Cod sursa(job #249257)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 27 ianuarie 2009 21:59:57
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <stdio.h>
#include <stdlib.h>

struct bil {
	int val, n1, n2;
};

bil x[1 << 20];
int a[128], n, s, nx, g = -1, dm;

void citire(void) {
	freopen("loto.in", "r", stdin);
	int i;

	scanf("%d%d", &n, &s);

	for (i = 1; i <= n; ++i) 
		scanf("%d", a+i);

	fclose(stdin);
}

void sumdo(void) {
	int i, j, k;

	for (i = 1; i <= n; ++i)
		for (j = i; j <= n; ++j)
			for (k = j; k <= n; ++k) {
				x[++nx].val = a[i] + a[j] + a[k];
				x[nx].n1 = a[i];
				x[nx].n2 = a[j];
			}
}

int partitie(int p,int r) {
	int piv, i = p-1, j = r+1;

	bil aux;
	piv = x[rand()%(r-p)+p].val;

	while (1) {
		do {++i;} while (x[i].val < piv);
		do {--j;} while (x[j].val > piv);
		if (i < j) {
			aux = x[i];
			x[i] = x[j];
			x[j] = aux;
		} else return j;
	}
}

void qsort(int p, int r) {
	if (p < r) {
		int q = partitie(p, r);
		qsort(p, q);
		qsort(q+1, r);
	}
}

void seek(void) {
	int i, p, j, t, o;

	for (i = 1; i <= nx; ++i){
		o = s - x[i].val;

		for (p = 1; p < nx; p <<= 1) ;
		for (j = 1; p; p >>= 1)
			if ((t = j + p) <= nx && x[t].val <= o)
				j = t;

		if (x[j].val == o) {
			printf("%d %d %d %d %d %d\n",
					x[i].n1, x[i].n2, x[i].val-x[i].n1-x[i].n2, 
					x[j].n1, x[j].n2, x[j].val-x[j].n1-x[j].n2);

			return;
		}
	}

	printf("-1\n");
}

int main(void) {

	citire();

	sumdo();

	qsort(1, nx);

	freopen("loto.out","w",stdout);

	seek();

	fclose(stdout);

	return 0;
}