Cod sursa(job #73963)

Utilizator andrei.12Andrei Parvu andrei.12 Data 22 iulie 2007 21:57:19
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<stdio.h>
#include<stdlib.h>
int n, suma, i, j, k, nr, sol = -1, v[105], t;
struct ches{
	int a, b, c;
};
ches w[1000005];
int caut(int x){
	int li = 1, ls = nr, p;
	while (li <= ls){
		p = (li+ls)/2;
		if (w[p].a == x)
			return p;
		else
			if (x < w[p].a)
				ls = p-1;
			else
				li = p+1;
	}
	return -1;
}
int comp(const void*xx, const void*yy){
	ches x = *(ches*)xx, y = *(ches*)yy;
	if (x.a < y.a) return -1;
	if (x.a > y.a) return 1;
	return 0;
}
int main()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d%d", &n, &suma);
	for (i=1; i<=n; i++)
		scanf("%d", &v[i]);
	nr = -1;
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++)
			for (k=1; k<=n; k++){
				w[++nr].a = v[i]+v[j]+v[k];
				w[nr].b = v[j];
				w[nr].c = v[k];
		}
	qsort(w, nr, sizeof(w[0]), comp);
	for (i=1; i<=nr; i++){
		sol = caut(suma-w[i].a);
		if (sol != -1)
			break;
	}
	if (sol != -1){
		t = w[i].a-w[i].b-w[i].c;
		printf("%d %d %d ", t, w[i].b, w[i].c);
		t = w[sol].a-w[sol].b-w[sol].c;
		printf("%d %d %d\n", t, w[sol].b, w[sol].c);
	}
	else
		printf("-1\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}