Cod sursa(job #1232573)

Utilizator vladrochianVlad Rochian vladrochian Data 23 septembrie 2014 12:47:59
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <vector>
using namespace std;
const int NMAX = 105, MOD = 666013;

struct PartSum {
	int s, x, y, z;
	PartSum(int ns, int nx, int ny, int nz) {
		s = ns;
		x = nx;
		y = ny;
		z = nz;
	}
};
int N, S, a[NMAX];
vector<PartSum> hsh[MOD];

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

PartSum Check(int s) {
	int crthash = s % MOD;
	for (size_t i = 0; i < hsh[crthash].size(); ++i)
		if (hsh[crthash][i].s == s)
			return hsh[crthash][i];
	return PartSum(-1, 0, 0, 0);
}

void Insert(const PartSum &nw) {
	if (Check(nw.s).s < 0)
		hsh[nw.s % MOD].push_back(nw);
}

int main() {
	fin >> N >> S;
	for (int i = 0; i < N; ++i)
		fin >> a[i];
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			for (int k = 0; k < N; ++k) {
				int s = a[i] + a[j] + a[k];
				PartSum crt(s, a[i], a[j], a[k]),
				        cmpl = Check(S - s);
				if (cmpl.s >= 0) {
					fout << cmpl.x << " "
					     << cmpl.y << " "
					     << cmpl.z << " "
					     << a[i] << " "
					     << a[j] << " "
					     << a[k] << "\n";
					return 0;
				}
				Insert(crt);
			}
	fout << "-1\n";
	return 0;
}