Cod sursa(job #744515)

Utilizator harababurelPuscas Sergiu harababurel Data 8 mai 2012 21:25:31
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 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, sol;
	
	f>>n>>s;
	
	for(i=1; i<=n; i++) {
		f>>k;
		nr.push_back(k);
	}
	
	sort(nr.begin(), nr.end());
	for(i=0; i<n; i++) {
		for(j=0; j<n; j++) {
			for(k=0; k<n; k++) {
				v.push_back(nr[i]+nr[j]+nr[k]);
			}
		}
	}
	
	sort(v.begin(), v.end());
	
	for(i=0; i<n; i++) {
		for(j=i; j<n; j++) {
			for(k=j; k<n; k++) {
				if(!gasit) {
					
					begin=-1;
					end=n;
					while(end-begin>1) {
						mid = begin + (end-begin)/2;
						
						if(v[mid] + nr[i] + nr[j] + nr[k] > s) begin=mid;
						else end=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) {
						sol.push_back(nr[i]);
						sol.push_back(nr[j]);
						sol.push_back(nr[k]);

						gasit=1;
					}
				}
			}
		}
	}
	
	sort(sol.begin(), sol.end());
	if(gasit) {
		for(i=0; i<=2; i++) g<<sol[i]<<" ";
		
		gasit=0;
		for(i=0; i<n; i++) {
			for(j=0; j<n; j++) {
				for(k=0; k<n; k++) {
					if(nr[i]+nr[j]+nr[k]==v[end]) {
						if(!gasit) {
						g<<nr[i]<<" "<<nr[j]<<" "<<nr[k];
						gasit=1;
						}
					}
				}
			}
		}
		
		
		g<<"\n";
	}
	else g<<"-1\n";
	
	
	f.close();
	g.close();
	return 0;
}