Cod sursa(job #542839)

Utilizator feelshiftFeelshift feelshift Data 27 februarie 2011 00:31:21
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
// http://infoarena.ro/problema/loto
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream in("loto.in");
ofstream out("loto.out");

vector<long long> input;
vector<long long> sum;

// calculeaza din nou sumele de trei numere
// pentru a descompune suma gasita
void write(long long toBeFound);

int main() {
	bool found = false;
	int number,dreamedSum,tmp;

	in >> number >> dreamedSum;
	for(int i=1;i<=number;i++) {
		in >> tmp;
		input.push_back(tmp);
	}

	// calculam toate sumele de trei numere
	// (suma cautate de noi, de sase numere,
	// va fi suma a doua sume de trei numere)
	vector<long long>::iterator first,second,third;
	for(first=input.begin();first!=input.end();first++)
		for(second=input.begin();second!=input.end();second++)
			for(third=input.begin();third!=input.end();third++)
				sum.push_back(*first+*second+*third);

	// sortam in ordine crescatoare
	sort(sum.begin(),sum.end());

	// cu iteratori depaseste timpul de executie
	int begin = 0;
	int end = sum.size() - 1;

	// parcurgem sumele de la capete pana acestea se intalnesc
	while(begin != end) {
		// daca suma cautata este mai mica
		while(sum[begin] + sum[end] > dreamedSum && end!=begin)
			// reducem intervalul in care cautam
			end--;

		// daca am gasit suma dorita
		if(sum[begin] + sum[end] == dreamedSum) {
			// calculam din nou sumele de trei numere
			// si afisam numerele
			write(sum[begin]);
			write(sum[end]);

			found = true;
			break;
		}

		if(found)
			break;

		// daca suma cautata este mai mare
		while(sum[begin] + sum[end] < dreamedSum && begin!=end)
			// reducem intervalul de cautare
			begin++;
	}

	if(!found)
		if(sum[begin] + sum[end] == dreamedSum) {
			write(begin);
			write(end);
		}
		else
			out << "-1";

	in.close();
	out.close();

	return (0);
}

void write(long long toBeFound) {
	vector<long long>::iterator first,second,third;
	for(first=input.begin();first!=input.end();first++)
		for(second=input.begin();second!=input.end();second++)
			for(third=input.begin();third!=input.end();third++)
				if(*first + *second + *third == toBeFound) {
					out << *first << " " << *second << " " << *third << " ";
					return;
				}
}