Cod sursa(job #130542)

Utilizator scvalexAlexandru Scvortov scvalex Data 1 februarie 2008 15:06:57
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int S(0),
	N(0);

vector<int> v;
vector<int> sv;

void print_back(int s, ostream &os) {
	for (int i(0); i < N; ++i)
		for (int j(0); j < N; ++j)
			for (int k(0); k < N; ++k)
				if (v[i] + v[j] + v[k] == s) {
					os << v[i] << " " << v[j] << " " << v[k];
					return;
				}
}

int main(int argc, char *argv[]) {
	ifstream fin("loto.in");
	fin >> N >> S;
	v.reserve(N);
	for (int i(0); i < N; ++i)
		fin >> v[i];
	fin.close();

	sort(v.begin(), v.end());

	set<int> sume;

	sv.reserve(N*N*N);
	int x(0);
	int aux;
	for (int i(0); i < N; ++i) {
		for (int j(0); j < N; ++j) {
			for (int k(0); k < N; ++k) {
				aux = v[i] + v[j] + v[k];
				if (sume.find(aux) == sume.end())
					//sume.insert(aux);
					sv[x++] = aux;
			}
		}
	}

	sort(sv.begin(), sv.end());

	int i(0);
	int j = N*N*N - 1;
	while (i < j) {
		while (sv[j] + sv[i] > S)
			--j;

		if (sv[i] + sv[j] == S) {
			ofstream fout("loto.out");
			print_back(sv[i], fout);
			fout << " ";
			print_back(sv[j], fout);
			fout << endl;
			fout.close();
			return 0;
		}

		++i;
	}

/*	for (set<int>::const_iterator it = sume.begin(); it != sume.end(); ++it) {
		if (sume.find(S - *it) != sume.end()) {
			ofstream fout("loto.out");
			print_back(*it, fout);
			fout << " ";
			print_back(S - *it, fout);
			fout << endl;
			fout.close();
			return 0;
		}
	}*/

	ofstream fout("loto.out");
	fout << -1 << endl;
	fout.close();

	return 0;
}