Cod sursa(job #749436)

Utilizator harababurelPuscas Sergiu harababurel Data 16 mai 2012 23:09:22
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 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, a, b, c, begin, end, mid, suma;
	vector <int> val, v;
	bool gasit=0;
	
	f>>n>>s;
	for(i=1; i<=n; i++) {
		f>>k;
		val.push_back(k);
	}
	
	for(i=0; i<int(val.size()); i++) 
		for(j=i; j<int(val.size()); j++) 
			for(k=j; k<int(val.size()); k++) 
				v.push_back(val[i]+val[j]+val[k]);	//combinatii de cate 3 valori

	
	sort(v.begin(), v.end());	//sortez ca sa pot cauta binar
	
	for(i=0; i<int(val.size()); i++) 
		for(j=i; j<int(val.size()); j++) 
			for(k=j; k<int(val.size()); k++) 
				if(!gasit) {
					suma = val[i] + val[j] + val[k];	//combinatii de alte 3 valori + cautare binara pentru cele calculate
	
					begin = -1;
					end = int(v.size());		//aici puneam n si era gresit
					while(end-begin>1) {
						mid = begin + (end-begin)/2;
						if( suma + v[mid] > s ) end = mid;
						else begin = mid;
					}
									
					if(v[mid] + suma == s) {	//am gasit numerele castigatoare
						g<<val[i]<<" "<<val[j]<<" "<<val[k]<<" ";	//pe 3 dintre ele le stiu
						
						for(a=0; a<int(val.size()); a++)		//la celelalte 3 stiu suma, asa ca le caut brut
							for(b=0; b<int(val.size()); b++)
								for(c=0; c<int(val.size()); c++)
									if(!gasit) {
										if(val[a]+val[b]+val[c]+suma==s) {
											g<<val[a]<<" "<<val[b]<<" "<<val[c]<<"\n";	//le-am gasit, nu mai caut
											gasit=1;
										}
									}
						gasit=1;
					}
				}
	
	
	if(!gasit) g<<"-1\n";
	
	f.close();
	g.close();
	return 0;
}