Cod sursa(job #140646)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 22 februarie 2008 01:17:30
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <algorithm>
#define MOD 43143
#define w(x) (x&((1u<<21)-1))
#define set(x) mask[w(x)/32] |= (1u<<(31&x));
#define isok(x) (mask[w(x)/32] & (1u<<(31&x)))

using namespace std;

struct {
	unsigned nr, next;
} h[MOD + (1<<18)];

unsigned a[100], n, s, N, aloc = MOD;
unsigned mask[1<<18];

void baga(unsigned x){
	unsigned key = x%MOD;
	while (h[key].next)
		key = h[key].next;
	h[key].nr = x;
	h[key].next = aloc++;
}

int exista(unsigned x){
	unsigned key = x%MOD;
	while (h[key].next){
		if (h[key].nr == x) return 1;
		key = h[key].next;
	}
	return 0;
}

int main(){
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);
	scanf("%d %d", &n, &s);
	for (unsigned i=0; i<n; i++)
		scanf("%d ", a+i);
	for (unsigned i=0; i<n; i++)
		for (unsigned j=i; j<n; j++)
			for (unsigned k=j; k<n; k++)
				set((s-a[i]-a[j]-a[k]));
	for (unsigned i=0; i<n; i++)
		for (unsigned j=i; j<n; j++)
			for (unsigned k=j; k<n; k++)
				if (isok((a[i]+a[j]+a[k]))) baga(a[i]+a[j]+a[k]);
	for (unsigned i=0; i<n; i++)
		for (unsigned j=i; j<n; j++)
			for (unsigned k=j; k<n; k++){
				unsigned poz = 0;
				if (!exista(s-a[i]-a[j]-a[k])) continue;
				for (unsigned p1=0; p1<n; p1++)
					for (unsigned p2=p1; p2<n; p2++)
						for (unsigned p3=p2; p3<n; p3++)
							if (a[p1]+a[p2]+a[p3] == s-a[i]-a[j]-a[k]){
								printf("%d %d %d %d %d %d", a[i], a[j], a[k], a[p1], a[p2], a[p3]);
								return 0;
							}
			}
	printf("-1");
}