Cod sursa(job #1052980)

Utilizator sp3ct3rFMI Dima Robert sp3ct3r Data 11 decembrie 2013 23:57:12
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <algorithm>
#include <iostream>

using namespace std;
struct suma
{
	int val, a, b;
};

bool bin_cprer(suma, suma);
bool cprer(suma, suma);

int main()
{
	int n, s;
	int *nr;
	suma *sume;
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);

	cin >> n >> s;
	nr = new int[n];
	sume = new suma[n*(n - 1) / 2 + n];
	for (int i = 0; i < n; ++i)
	{
		cin >> nr[i];
	}
	int ctr = 0;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i; j < n; ++j)
		{
			sume[ctr].a = i;
			sume[ctr].b = j;
			sume[ctr].val = nr[i] + nr[j];
			++ctr;
		}
	}

	sort(sume, sume + ctr-1, cprer);

	bool found = false;
	for (int i = 0; i < ctr; ++i)
	{
		if (s - sume[i].val < 0)
			break;
		for (int j = i; j < ctr; ++j)
		{
			suma csum;
			csum.val = s - sume[i].val - sume[j].val;
			if (csum.val < 0)
			{
				break;
			}
			if (binary_search(sume, sume + ctr - 1, csum, bin_cprer))
			{
				cout << nr[sume[i].a] << " " << nr[sume[i].b] << " " << nr[sume[j].a] << " " << nr[sume[j].b];

				for (int k = 0; k < j; k++)
				{
					if (sume[k].val == csum.val)
					{
						cout << " " << nr[sume[k].a] << " " << nr[sume[k].b];
						found = true;
						break;
					}
				}
			}
			if (found) break;
		}
		if (found) break;
	}
	if (!found) cout << "-1";
}

bool bin_cprer(suma a, suma b)
{
	return a.val < b.val;
}

bool cprer(suma a, suma b)
{
	if (a.val < b.val)
	{
		return true;
	}
	else return false;
}