Cod sursa(job #14821)

Utilizator vmaneavmanea vmanea Data 9 februarie 2007 21:50:45
Problema Loto Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <stdio.h>
#include <stdlib.h>
#define nmax 105
#define milion 1000005

int N,S,i,j,k,l,m,n, ok,S2,f,dif,a,b,c;
int V[nmax], X[nmax];
int VS[4][milion], VS2[4][milion];

void msort(int, int);
void msort2(int, int);
int cauta(int, int *, int *, int *);

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

	scanf("%d%d", &N, &S);
	for (i = 1; i <= N; ++i)
		scanf("%d", &V[i]);

	msort(1, N);

	for (i = k = 1; i <= N; ++i)
		if (V[i] != V[i - 1])
		{
			X[k] = V[i];
     			++k;
		}

	N = --k;

	S2 = S;

	for (i = 1; i <= N && 3 * X[i] <= S2; ++i)
	 for (j = i; j <= N && X[i] + 2 * X[j] <= S2; ++j)
	  for (k = j; k <= N && X[i] + X[j] + X[k] <= S2; ++k)
	  {
		++f;
		VS[0][f] = X[i] + X[j] + X[k];
		VS[1][f] = X[i];
		VS[2][f] = X[j];
		VS[3][f] = X[k];
	  }

	msort2(1, f); // am nevoie de sortare

	for (i = (k = 0) + 1; i <= f; ++i)
		if (VS[0][i] != VS[0][i - 1])
		{
			++k;
			VS2[0][k] = VS[0][i];
			VS2[1][k] = VS[1][i];
			VS2[2][k] = VS[2][i];
			VS2[3][k] = VS[3][i];
		}

	for (i = 1; i <= k; ++i)
	{
		dif = S - VS2[0][i];
		if (cauta(dif, &a, &b, &c))
		{
			printf("%d %d %d %d %d %d\n", VS2[1][i], VS2[2][i], VS2[3][i], a, b, c);
			return 0;
		}
	}

	printf("-1\n");
	return 0;

/*
	75p

	N = k;
	for (i = N; i <= N && 6 * X[i] <= S; ++i)
	 for (j = i; j <= N && X[i] + 5 * X[j] <= S; ++j)
	  for (k = j; k <= N && X[i] + X[j] + 4 * X[k] <= S; ++k)
	   for (l = k; l <= N && X[i] + X[j] + X[k] + 3 * X[l] <= S; ++l)
	    for (m = l; m <= N && X[i] + X[j] + X[k] + X[l] + 2 * X[m] <= S; ++m)
	     for (n = m; n <= N && X[i] + X[j] + X[k] + X[l] + X[m] + X[n] <= S; ++n)
	      if (X[i] + X[j] + X[k] + X[l] + X[m] + X[n] == S)
	      {
		printf("%d %d %d %d %d %d\n", X[i], X[j], X[k], X[l], X[m], X[n]);
		return 0;
	      }
	printf("-1\n");
	return 0;
	*/

}

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

	if (l >= r) return;

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

	for (i = k = l, j = m + 1; i <= m && j <= r; ++k)
		if (VS[0][i] <= VS[0][j])
		{
			VS2[0][k] = VS[0][i];
			VS2[1][k] = VS[1][i];
			VS2[2][k] = VS[2][i];
			VS2[3][k] = VS[3][i];
			++i;
		}
		else
		{
			VS2[0][k] = VS[0][j];
			VS2[1][k] = VS[1][j];
			VS2[2][k] = VS[2][j];
			VS2[3][k] = VS[3][j];
			++j;
		}

	for (; i <= m; ++i, ++k)
	{
			VS2[0][k] = VS[0][i];
			VS2[1][k] = VS[1][i];
			VS2[2][k] = VS[2][i];
			VS2[3][k] = VS[3][i];
	}

	for (; j <= r; ++j, ++k)
	{
			VS2[0][k] = VS[0][j];
			VS2[1][k] = VS[1][j];
			VS2[2][k] = VS[2][j];
			VS2[3][k] = VS[3][j];
	}

	for (i = l; i <= r; ++i)
	{

			VS[0][i] = VS2[0][i];
			VS[1][i] = VS2[1][i];
			VS[2][i] = VS2[2][i];
			VS[3][i] = VS2[3][i];
	}
}

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

	if (l >= r) return;

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

	for (i = k = l, j = m + 1; i <= m && j <= r; ++k)
		if (V[i] <= V[j])
			X[k] = V[i++];
		else
			X[k] = V[j++];

	for (; i <= m; ++i, ++k)
		X[k] = V[i];

	for (; j <= r; ++j, ++k)
		X[k] = V[j];

	for (i = l; i <= r; ++i)
		V[i] =X[i];
}

int cauta(int val, int *a, int *b, int *c)
{
	int l,r;

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

		if (VS2[0][m] == val)
		{
			*a = VS2[1][m];
			*b = VS2[2][m];
			*c = VS2[3][m];

			return 1;
		}
		else if (VS2[0][m] > val)
			r = m - 1;

		     else
			l = m + 1;
	}

	return 0;
}