Cod sursa(job #568051)

Utilizator rootsroots1 roots Data 30 martie 2011 19:40:50
Problema Loto Scor 10
Compilator cpp Status done
Runda 102 Marime 0.95 kb
#include <stdio.h>

#define MOD 999983
#define Dim 105

struct hash
{
	int i1,i2,i3;
	hash *link;
}*H[MOD+5];

int v[Dim];

void add(int a,int b,int c,int x)
{
	hash *p;

	p=new hash;
	p->i1=a;
	p->i2=b;
	p->i3=c;
	p->link=H[x];
	H[x]=p;
}

int main()
{
	int x,S,N,i,j,k;
	hash *p;

	freopen("loto.in","r",stdin);

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

	freopen("loto.out","w",stdout);

	if(v[N]*6<S)
	{
		printf("-1\n");
		return 0;
	}

	for(i=1;i<=N;i++)
		for(j=i;j<=N;j++)
			for(k=j;k<=N;k++)
			{
				x=v[i]+v[j]+v[k];
				add(v[i],v[j],v[k],x%MOD);
			}

	for(i=1;i<=N;i++)
		for(j=i;j<=N;j++)
			for(k=j;k<=N;k++)
			{
				x=v[i]+v[j]+v[k];
				p=H[(S-x)%MOD];
				while(p)
				{
					if(p->i1+p->i2+p->i3==S-x)
					{
						printf("%d %d %d %d %d %d\n",v[i],v[j],v[k],p->i1,p->i2,p->i3);
						return 0;
					}
					p=p->link;
				}
			}

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