Cod sursa(job #64702)

Utilizator gigi_becaliGigi Becali gigi_becali Data 4 iunie 2007 23:30:49
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
using namespace std;
#include <cstdio>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#define rnd (rand()%66600013)
#define oo 0x3f3f3f3f
#define maxn 128

struct nod { int x, y, z, p; nod *s, *d;};
nod *r, *nil;
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);
}

void init()
{
	srand(time(0));
	r=nil=new nod;
	nil->x=nil->y=nil->z=nil->p=-oo;
	nil->s=nil->d=0;
}

int find(nod *&n,int sum,nod *&f)
{
	if(n==nil) 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, int p)
{
	if(n==nil)
	{
		n=new nod;
		n->s=n->d=nil;
		n->x=x; n->y=y; n->z=z;n->p=p;
		return;
	}
	int s=n->x+n->y+n->z, sum=x+y+z;
	if(s>sum)
	{
		insert(n->s, x, y, z, p); 
		if(n->s->p>n->p) rots(n);
	}
		
	if(s<sum)
	{
		insert(n->d, x, y, z, p);
		if(n->d->p>n->p) rotd(n);		
	}
}
	

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


int main()
{
	init();
	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], rnd);

	//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;
}