Cod sursa(job #93876)

Utilizator gigi_becaliGigi Becali gigi_becali Data 20 octombrie 2007 15:38:04
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <algorithm>
#define maxn 666757
#define oo 0x3f3f3f3f
using namespace std;	
struct nod { int a, b, c,v; nod *l, *r;};

typedef nod*  tree;
tree H[maxn],nil;
int A, B, C;
int a[128];

void init()
{
	nil=new nod;
	nil->l=nil->r=0;
	nil->v=oo;
	for(int i=0;i<maxn;++i) H[i]=new nod, H[i]=nil;
}

void ins(tree &n, int a, int b, int c)
{
	if(n==nil)
	{	
		n=new nod;
		n->a=a; n->b=b; n->c=c; n->v=a+b+c;
		n->l=n->r=nil;
		return ;
	}
	
	if(a+b+c<n->v) ins(n->l, a, b, c);
	if(a+b+c>n->v) ins(n->r, a, b, c);
}

int find(tree n, int v)
{
	if(n==nil)return 0;
	if(v<n->v) return find(n->l, v);
	if(v>n->v) return find(n->r, v);
	if(v==n->v) 
	{	A=n->a; B=n->b; C=n->c; return 1;}
	return 0;
}

inline int insert(int a, int b, int c)
{
	ins(H[(a+b+c)%maxn], a, b, c);
}

inline int find(int v)
{
	if(v<0)return 0;
	return find(H[v%maxn], v);
}

int main()
{
	int n, S;
	init();
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d %d\n", &n, &S);
	for(int i=1;i<=n;++i) scanf("%d ", a+i);
	
	int i, j, k;
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
			for(k=1;k<=n;++k)
				insert(a[i], a[j], a[k]);



	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
			for(k=1;k<=n;++k)
			{
				int s=S-a[i]-a[j]-a[k];
				if(find(s)) 
				{
					int q[7];
					q[1]=a[i];
					q[2]=a[j];	
					q[3]=a[k];
					q[4]=A;
					q[5]=B;
					q[6]=C;
					//sort(q+1, q+6+1);
					for(int t=1;t<=6;++t)printf("%d ", q[t]);
					printf("\n");
					return 0;
					
				}
			}

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