Cod sursa(job #73970)

Utilizator andrei.12Andrei Parvu andrei.12 Data 23 iulie 2007 08:47:42
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
#include<stdlib.h>
int n, suma, j, k, nr, sol = -1, v[105], t;
struct ches{
	int a, b, c;
};
ches w[1000005];
int caut(int val)   
{   
    int i, step;   
    for (step = 1; step < nr; step <<= 1);   
    for (i = 0; step; step >>= 1)   
        if (i + step < nr && w[i + step].a <= val)   
           i += step;   
    return i;   
}   

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);
	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].a = v[i]+v[j]+v[k];
				w[nr].b = v[j];
				w[nr].c = v[k];
		}
	qsort(w, nr+1, sizeof(w[0]), comp);
	if (w[1].a+w[nr].a < suma){
		printf("-1\n");
		return 0;
	}
	for (i=1; i<=nr; i++){
		sol = caut(suma-w[i].a);
		
		if (w[sol].a == suma-w[i].a)
			break;
		else
			if (w[i].a > suma-w[i].a){
				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;
}