Cod sursa(job #744522)

Utilizator harababurelPuscas Sergiu harababurel Data 8 mai 2012 21:42:27
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ifstream f("loto.in");
	ofstream g("loto.out");
	
	int n, s, i, j, k, begin, end, mid;
	bool gasit=0;
	vector <int> v, nr;
	
	f>>n>>s;
	
	for(i=1; i<=n; i++) {
		f>>k;
		nr.push_back(k);
	}
	
	for(i=0; i<n; i++) {
		for(j=i; j<n; j++) {
			for(k=j; k<n; k++) {
				v.push_back(nr[i]+nr[j]+nr[k]);
				
			}
		}
	}
	
	sort(v.begin(), v.end());
	gasit=0;
	
	for(i=0; i<n; i++) {
		for(j=0; j<n; j++) {
			for(k=0; k<n; k++) {
				if(!gasit) {
					
					begin=-1;
					end=n;
					while(end-begin>1) {
						mid = (begin + end)/2;
						
						if(v[mid] + nr[i] + nr[j] + nr[k] > s) end=mid;
						else begin=mid;
					}
					
				//	if(v[begin] + nr[i] + nr[j] + nr[k] == s) end=begin;
				//	if(v[mid] + nr[i] + nr[j] + nr[k] == s) end=mid;
				//	if(v[end+1] + nr[i] + nr[j] + nr[k] == s) end++;
				//	if(v[end-1] + nr[i] + nr[j] + nr[k] == s) end--;
					
					
					
					if(v[end] + nr[i] + nr[j] + nr[k] == s) {
						g<<nr[i]<<" "<<nr[j]<<" "<<nr[k]<<" ";
						s-= (nr[i]+nr[j]+nr[k]);
						gasit=1;
					}
				}
			}
		}
	}
	if(!gasit) g<<"-1\n";
	
	if(gasit) {
		
		gasit=0;
		for(i=0; i<n; i++) {
			for(j=i; j<n; j++) {
				for(k=j; k<n; k++) {
					if(!gasit) {
						if(nr[i]+nr[j]+nr[k]==s) {
							g<<nr[i]<<" "<<nr[j]<<" "<<nr[k]<<"\n";
							gasit=1;
						}
						
					}
				}
			}
		}
	}

	
	
	
	f.close();
	g.close();
	return 0;
}