Cod sursa(job #494709)

Utilizator The_DisturbedBungiu Alexandru The_Disturbed Data 22 octombrie 2010 18:06:35
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct point
{
	int x;
	short a,b,c;
	point *y;
};
point *a[100000],*p,*w;
int m,n,i,j,k,v[102],q,max;
long s;
bool found;
int h(int k)
{
	float c;
	c=(sqrt(5)+1)/2;
	return (int)(m*((k*c)-(int)(k*c)))%100000;
}
void ins(int nr)
{
	int q;
	p=new point;
	q=h(nr);
	if(q>max)max=q;
	p->x=nr;
	p->a=i;
	p->b=j;
	p->c=k;
	p->y=a[q];
	a[q]=p;
}
point* search(int x)
{
	point *p;
	int i;
	i=h(x);
	p=a[i];
	while(p&&p->x!=x) p=p->y;
	if(!p)return NULL;
	if(p->x==x)return p;
}
int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d%ld",&n,&s);
	max=0;
	for(i=0;i<n;i++)scanf("%d",&v[i]);
	m=(n*n*n)/3;
	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
			for(k=j;k<n;k++)
			{
				q=v[i]+v[j]+v[k];
				ins(q);
			}
	i=0;
	found=0;
	while(!found&&i<max)
	{
		p=a[i];
		while(p)
		{
			w=search(s-(p->x));
			if(w)
			{
				found=1;
				printf("%d %d %d %d %d %d",v[p->a],v[p->b],v[p->c],v[w->a],v[w->b],v[w->c]);
				break;
			}
			p=p->y;
		}
		i++;
	}
	if(!found)printf("-1");
	return 0;
}