Cod sursa(job #792537)

Utilizator zdrobau_valeriuZdrobau Valeriu zdrobau_valeriu Data 27 septembrie 2012 14:59:20
Problema Loto Scor 100
Compilator cpp Status done
Runda asem-etapa1 Marime 1.94 kb
#include <stdio.h>
#define nmax 100

int N, M, W, ok;

int A[nmax];

int S[nmax*nmax*nmax], E[2][nmax*nmax*nmax];

int S2[nmax*nmax*nmax], E2[2][nmax*nmax*nmax];

void read();
void solve();
void write();
int bs(int);

int main()
{
	read();

	solve();

	write();

	return 0;
}

void read()
{
	int i;

	freopen("loto.in", "r", stdin);
	scanf("%d%d", &N, &W);
	for (i = 1; i <= N; ++i)
		scanf("%d", A+i);

}

void msort(int l, int r)
{
	if (l >= r) return;

	int m = (l+r)>>1, i, j, k;


	msort(l, m);
	msort(m+1, r);

	for (i = k = l, j = m+1; i <= m && j <= r; ++k)
	{
		if (S[i] < S[j])
		{
			S2[k] = S[i];
			E2[0][k] = E[0][i];
			E2[1][k] = E[1][i];
			++i;
		}
		else
		{
			S2[k] = S[j];
			E2[0][k] = E[0][j];
			E2[1][k] = E[1][j];
			++j;
		}
	}

	for (; i <= m; ++k)
	{
		S2[k] = S[i];
		E2[0][k] = E[0][i];
		E2[1][k] = E[1][i];
		++i;
	}

	for (; j <= r; ++k)
	{
		S2[k] = S[j];
		E2[0][k] = E[0][j];
		E2[1][k] = E[1][j];
		++j;
	}

	for (k = l; k <= r; ++k)
	{
		S[k] = S2[k];
		E[0][k] = E2[0][k];
		E[1][k] = E2[1][k];
	}
}

void solve()
{
	int i, j, k;

	freopen("loto.out", "w", stdout);

	for (i = 1; i <= N; ++i)
		for (j = i; j <= N; ++j)
			for (k = j; k <= N; ++k)
			{
				S[++M] = A[i]+A[j]+A[k];
				E[0][M] = A[i];
				E[1][M] = A[j];
			}

	msort(1, M);
}

int bs(int x)
{
	int l, r, m;

	for (l = 1, r = M; l <= r; )
	{
		m = (l+r) >> 1;

		if (S[m] == x)
			return m;
		if (S[m] < x)
			l = m+1;
		else
			r = m-1;
	}

	return 0;
}

void write()
{
	int i, j, k, ok=0, x;

	for (i = 1; i <= N && !ok; ++i)
		for (j = i; j <= N && !ok; ++j)
			for (k = j; k <= N && !ok; ++k)
			{
				if(W-A[i]-A[j]-A[k] > 0 && (x = bs(W-A[i]-A[j]-A[k])))
				{
					printf("%d %d %d %d %d %d\n", E[0][x], E[1][x], A[i], A[j], A[k], W-A[i]-A[j]-A[k]-E[0][x]-E[1][x]);
					ok = 1;
				}
			}

	if (!ok)
		printf("-1\n");
}