Cod sursa(job #489339)

Utilizator ZethpixZethpix Zethpix Data 2 octombrie 2010 12:03:04
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>

struct list
{
	long x,y,z,s;
	list *link;
}*H[500002],*p;

long i,j,k,m,n,pow,S,x,ok,v[102],s;

void addlink(long pos,long s,long x,long y,long z)
{
	list *p;
	p=new list;
	p->s=s;
	p->x=x;
	p->y=y;
	p->z=z;
	p->link=H[pos];
	H[pos]=p;
}

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

	scanf("%ld%ld",&n,&S);
	for(i=1;i<=n;i++)
		scanf("%ld",&v[i]);

	if(n==1)
	{
		if(S/v[n]==6&&S%v[n]==0) printf("%ld %ld %ld %ld %ld %ld\n",v[n],v[n],v[n],v[n],v[n],v[n]);
		else printf("-1\n");
		return 0;
	}
	m=(n*n*n)/3;
	pow=1;
	while(pow<=m) pow*=2;
	m=(pow/2+pow)/2;
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
			{
				s=v[i]+v[j]+v[k];
				x=s%m;
				addlink(x,s,v[i],v[j],v[k]);
			}

	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			for(k=j;k<=n;k++)
			{
				s=v[i]+v[j]+v[k];
				if(s<=S)
				{
					x=(S-s)%m;
					p=H[x];
					ok=1;
					while(p!=NULL)
					{
						if(p->s==S-s)
						{
							ok=0;
							break;
						}
						p=p->link;
					}
					if(ok==0)
					{
						printf("%ld %ld %ld %ld %ld %ld\n",v[i],v[j],v[k],p->x,p->y,p->z);
						return 0;
					}
				}
			}

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