Cod sursa(job #74294)

Utilizator andrei.12Andrei Parvu andrei.12 Data 24 iulie 2007 19:12:46
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<stdio.h>
#include<stdlib.h>
#define lg 1000005
int n, suma, j, k, nr, sol = -1, v[105], t, i, sort[lg];
struct ches{
	int a, b, c;
};
ches w[lg], w1[lg];
int caut(int x){
	int li = i, 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){
	int *xxx = (int*)xx, *yyy = (int*)yy;
	int x = *xxx, y = *yyy;
	if (w1[x].a < w1[y].a) return -1;
	if (w1[x].a > w1[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 = 0;
	for (i=1; i<=n; i++)
		for (j=i; j<=n; j++)
			for (k=j; k<=n; k++){
				w1[++nr].a = v[i]+v[j]+v[k];
				w1[nr].b = v[j];
				w1[nr].c = v[k];
		}
	for (i=1; i<=nr; i++)
		sort[i] = i;
	qsort(sort, nr+1, sizeof(sort[0]), comp);
	for (i=1; i<=nr; i++){
		w[i].a = w1[sort[i]].a;
		w[i].b = w1[sort[i]].b;
		w[i].c = w1[sort[i]].c;
	}
	for (i=1; i<=nr; i++){
		if (suma - w[i].a < w[i].a)
			break;
		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;
}