Cod sursa(job #64656)

Utilizator gigi_becaliGigi Becali gigi_becali Data 4 iunie 2007 18:02:05
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
using namespace std;
#include <cstdio>
#include <algorithm>
#define maxn 128

struct nod { int x, y, z; nod *s, *d;};
nod *r;
int N, S, x[maxn];

void citire()
{
	freopen("loto.in", "r", stdin);
	scanf("%d %d\n", &N, &S);
	for(int i=1;i<=N;++i) scanf("%d ", x+i);
}

int find(nod *&n,int sum,nod *&f)
{
	if(!n) return 0;
	int s=n->x+n->y+n->z;
	if(s==sum) { f=n; return 1;}
	if(s>sum) return find(n->s, sum, f);
	else return find(n->d, sum, f);
	return 0;
}

inline void  rots(nod *&n)
{
	nod *t=n->s;
	n->s=t->d; t->d=n; n=t;
}

inline void rotd(nod *&n)
{
	nod *t=n->d;
	n->d=t->s; t->s=n; n=t;
}


void insert(nod *&n, int x, int y, int z)
{
	if(!n)
	{
		n=new nod;
		n->s=n->d=0;
		n->x=x; n->y=y; n->z=z;
		return;
	}
	int s=n->x+n->y+n->z, sum=x+y+z;
	if(s>sum)
	{
		if(n->s) insert(n->s, x, y, z);//, rots(n);
		else
		{
			nod *t=new nod; 
			t->x=x; t->y=y; t->z=z;
			t->s=t->d=0;
			n->s=t;
		}
		
	}
	if(s<sum)
	{
		if(n->d) insert(n->d, x, y, z);//, rotd(n);
		else
		{
			nod *t=new nod;
			t->x=x; t->y=y; t->z=z;
			t->s=t->d=0;
			n->d=t;
		}
		
	}
}
	

void ino(nod *n)
{
	if(n->s) ino(n->s);
	printf("%d %d %d\n", n->x, n->y, n->z);
	if(n->d) ino(n->d);
}


int main()
{
	citire();
	freopen("loto.out", "w", stdout);
	int i, j, k;
	nod *p;
	for(i=1;i<=N;++i)
		for(j=1;j<=N;++j) 
			for(k=1;k<=N;++k) insert(r, x[i], x[j], x[k]);

	//ino(r);
	int s;
	for(i=1;i<=N;++i)
		for(j=1;j<=N;++j)
			for(k=1;k<=N;++k)
			{
				s=x[i]+x[j]+x[k];
				if(find(r, S-	s, p))
				{
					int st[7], w=0;
			//		printf("%d %d %d\n", x[i], x[j], x[k]);
					st[++w]=x[i];
					st[++w]=x[j];
					st[++w]=x[k];
					st[++w]=p->x;
					st[++w]=p->y;
					st[++w]=p->z;
					sort(st+1, st+w+1);
					for(int q=1;q<=w;++q) printf("%d ",st[q]);
					printf("\n");
					return 0;
				}
			}
	printf("-1\n");
	return 0;
}