Cod sursa(job #221812)

Utilizator ilincaSorescu Ilinca ilinca Data 18 noiembrie 2008 10:06:06
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <algorithm>

#define maxn 105
#define maxs 600000005
#define pr(x) fprintf(stderr,#x" = %d\n",x)

using namespace std;

struct bilet
{
	int x, y, z, s;
};

bilet b [maxn*maxn*maxn];
int a, n, S, ns, poz [maxn*maxn*maxn], v [maxn];


void scan ()
{
	int i;
	scanf ("%d%d", &n, &S);
	for (i=1; i<=n; ++i)
		scanf ("%d", &v [i]);
}

void sume ()
{
	int i, j, k;
	for (i=1; i<=n; ++i)
		for (j=i; j<=n; ++j)
			for (k=j; k<=n; ++k)
			{
				b [++ns].x=i;
				b [ns].y=j;
				b [ns].z=k;
				b [ns].s=v [i]+v [j]+v [k];
			}
}

void init ()
{
	int i;
	for (i=1; i<=ns; ++i)
		poz [i]=i;
	for (a=1; a<=ns; a<<=1);
}

int comp (const void *x, const void *y)
{
	int xx, yy;
	xx=* (int *)x;
	yy=* (int *)y;
	if (b [xx].s < b [yy].s)
		return -1;
	if (b [xx].s > b [yy].s)
		return 1;
	return 0;
}

int bs (int V)
{
	int i, ca=a;
	for (i=0; a; a>>=1)
	{
		if (b [poz [a+i]].s <= V && i+a <= ns)
			i+=a;
	}
	a=ca;
	if (b [poz [i]].s == V)
		return i;
	return 0;
}

void rez ()
{
	int i, j, k, w;
	for (i=1; i<=n; ++i)
		for (j=i; j<=n; ++j)
			for (k=j; k<=n; ++k)
			{
				w=bs (S-v [i]-v [j]-v [k]);
				if (w)
				{
					printf ("%d %d %d %d %d %d\n", v [i], v [j] , v [k], v [b [poz [w]].x], v [b [poz [w]].y], v [b [poz [w]].z]);
					return;
				}
			}
	printf ("-1\n");
}

int main ()
{
	freopen ("loto.in", "r", stdin);
	freopen ("loto.out", "w", stdout);
	scan ();
	sume ();
	init ();
	qsort (poz+1, ns, sizeof (int), comp);
	rez ();
	return 0;
}