Cod sursa(job #135281)

Utilizator scvalexAlexandru Scvortov scvalex Data 13 februarie 2008 14:05:41
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

int S(0),
	N(0);

vector<int> v;
int ord[1000001];

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 cmp(const void *a, const void *b) {
	return *(int*)a - *(int*)b;
}

int main(int argc, char *argv[]) {
	FILE *fin = fopen("loto.in", "r");
	fscanf(fin, "%d %d", &N, &S);
	v.reserve(N);
	for (int i(0); i < N; ++i)
		fscanf(fin, "%d", &v[i]);
	fclose(fin);

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

	int n(0);
	for (int i(0); i < N; ++i) {
		for (int j(0); j < N; ++j) {
			for (int k(0); k < N; ++k) {
				ord[n++] = v[i] + v[j] + v[k];
			}
		}
	}

	//qsort(ord, n, sizeof(ord[0]), cmp);
	sort(ord, ord + n);

	int p(0),
		q = n - 1;

	while (p <= q) {
		while ((q >= 0) && (ord[p] + ord[q] > S))
			--q;

		if (q < 0)
			break;

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

		++p;
	}

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

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

	return 0;
}