Cod sursa(job #533150)

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

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

vector<int> input;
vector<int> sum;

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

int main() {
	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<int>::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]);

			return (0);
		}

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

	out << "-1\n";

	return (0);
}

void write(int toBeFound) {
	vector<int>::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;
				}
}