Cod sursa(job #749433)

Utilizator harababurelPuscas Sergiu harababurel Data 16 mai 2012 23:04:28
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define x first
#define y second
#define ll int
using namespace std;


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