Cod sursa(job #494552)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 21 octombrie 2010 22:09:30
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <stdio.h>
#include <stdlib.h>

struct point {
	long a,b,c;
	point *leg;
};
point *h[500000];
long s,s1,s2,i,j,k,nr,x,v[101],n1,a1,b1,c1;
int n,ok;

void insert(long a1, long b1, long c1, long x) {
	point *p;
	p=new point;
	p->a=a1; 
	p->b=b1;
	p->c=c1;
	p->leg=h[x];
	h[x]=p;
}

int chash(point *p,long s2,long &a1,long &b1,long &c1) {
	int ok;
	ok=0;
	while (p!=NULL) 
		if (s2==((p->a)+(p->b)+(p->c))) {
			a1=p->a;
			b1=p->b;
			c1=p->c;
			return 1;
		}
	    else p=p->leg;
	return 0;
}

/* int cautare(int i) {
	int ok,a1,b1,c1;
	ok=0;
	while (h[i]!=NULL) {
		s2=s-((h[i]->a)+(h[i]->b)+(h[i]->c));
		x=s2%n1;
		a1=b1=c1=0;
		ok=chash(h[x],s2,a1,b1,c1);
		if (ok) {
			printf("%ld %ld %ld %ld %ld %ld\n",h[i]->a,h[i]->b,h[i]->c,a1,b1,c1);
			return 1;
		}
		h[i]=h[i]->leg;
	}
	return 0;
} */

void creare(long &n1) {
	long m,x;
	m=(n*n*n)/3;
    x=1;
    while(x<=m) x*=2;
    m=(x/2+x)/2;
	n1=m;
}

int main () {
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d%ld",&n,&s);
	n1=0;
	creare(n1);
	for (i=1; i<=n; i++) scanf("%ld",&v[i]);
	if (n==1) 
		if (s%v[1]==0) {
			for (i=1; i<=6; i++) printf("%ld ",v[1]);
			return 0;
		}
		else { 
			printf("-1\n");
			return 0;
		}

	for (i=1; i<=n; i++) 
		for (j=i; j<=n; j++)
			for (k=j; k<=n; k++) {
				nr=v[i]+v[j]+v[k];
				x=nr%n1;
				insert(v[i],v[j],v[k],x);
			}
	
	a1=b1=c1=0;
	for (i=1; i<=n; i++) 
		for (j=i; j<=n; j++)
			for (k=j; k<=n; k++) {
				s1=v[i]+v[j]+v[k];
				if (s1<s) {
					s2=s-s1;
					x=s2%n1;
					ok=chash(h[x],s2,a1,b1,c1);
					if (ok) {
						printf("%ld %ld %ld %ld %ld %ld",v[i],v[j],v[k],a1,b1,c1);
					    return 0;
				    }
				}
			}
			
	/* for (i=0; i<=n1; i++) {
		ok=0;
		ok=cautare(i);
		if (ok) break;
	} */
	if (!ok) printf("-1");
	return 0;
}