Cod sursa(job #249223)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 27 ianuarie 2009 21:30:28
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 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 = 1; j <= n; ++j)
			for (k = 1; 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, b, e, m, o;

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

		while (b != e) {
			m = (b+e) >> 1;
			if (x[m].val < o) 
				b = m+1; 
			else 
				e = m;
		}

		if (x[b].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[b].n1, x[b].n2, x[b].val-x[b].n1-x[b].n2);

			return;
		}
	}

	printf("-1\n");
}

int main(void) {

	citire();

	sumdo();

	qsort(1, nx);

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

	seek();

	fclose(stdout);

	return 0;
}