Cod sursa(job #249171)

Utilizator victorsbVictor Rusu victorsb Data 27 ianuarie 2009 20:20:26
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define Nmax 105

class tri
{
public:
	int x, y, z;

	void init(int a, int b, int c)
	{
		x = a, y = b, z = c;
	}
	int sum()
	{
		return x + y + z;
	}
};

int N, S, ct;
int val[Nmax];
tri sir[Nmax * Nmax * Nmax];

void citire()
{
	scanf("%d%d", &N, &S);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &val[i]);
}

int cmp(tri A, tri B)
{
	return A.sum() < B.sum();
}

void solve()
{
	for (int i = 1; i <= N; ++i)
		for (int j = i; j <= N; ++j)
			for (int k = j; k <= N; ++k)
				sir[++ct].init(val[i], val[j], val[k]);

	sort(sir + 1, sir + ct + 1, cmp);

	for (int i = 1; i <= N; ++i)
		for (int j = i; j <= N; ++j)
			for (int k = j; k <= N; ++k)
			{
				int S1 = S - val[i] - val[j] - val[k];
				int st = 1, dr = ct;
				while (st <= dr)
				{
					int mij = (st + dr) / 2;
					if (sir[mij].sum() == S1)
					{
						printf("%d %d %d %d %d %d\n", val[i], val[j], val[k], sir[mij].x, sir[mij].y, sir[mij].z);
						return;
					}
					if (sir[mij].sum() < S1)
						st = mij + 1;
					else
						dr = mij - 1;
				}
			}
	printf("-1\n");
}

int main()
{
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);

	citire();
	solve();

	return 0;
}