Cod sursa(job #14808)

Utilizator vmaneavmanea vmanea Data 9 februarie 2007 21:05:24
Problema Loto Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#include <stdlib.h>
#define nmax 105

int N,S,i,j,k,l,m,n, ok;
int V[nmax], X[nmax];

void msort(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 = 0) + 1; i <= N; ++i)
		if (V[i] != V[i - 1])
			X[++k] = V[i];

	N = k;

	for (i = 1; i <= N && !ok && 6 * X[i] <= S; ++i)
	 for (j = i; j <= N && !ok && X[i] + 5 * X[j] <= S; ++j)
	  for (k = j; k <= N && !ok && X[i] + X[j] + 4 * X[k] <= S; ++k)
	   for (l = k; l <= N && !ok && X[i] + X[j] + X[k] + 3 * X[l] <= S; ++l)
	    for (m = l; m <= N && !ok && X[i] + X[j] + X[k] + X[l] + 2 * X[m] <= S; ++m)
	     for (n = m; n <= N && !ok && 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]);
		ok = 1;
	      }

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

	return 0;
}

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)
		X[k++] = V[i++];

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

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