Cod sursa(job #489302)

Utilizator ZethpixZethpix Zethpix Data 2 octombrie 2010 11:15:27
Problema Loto Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

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

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

void addlink(int pos,int s,int x,int y,int 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("%d%d",&n,&S);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);

	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=1;j<=n;j++)
			for(k=1;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];
				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("%d %d %d %d %d %d\n",v[i],v[j],v[k],p->x,p->y,p->z);
					return 0;
				}
			}

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