Cod sursa(job #73971)

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