Cod sursa(job #73969)

Utilizator andrei.12Andrei Parvu andrei.12 Data 23 iulie 2007 08:38:05
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 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 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 caut(int val)   
{   
    int i, step;   
    for (step = 1; step < n; step <<= 1);   
    for (i = 0; step; step >>= 1)   
        if (i + step < n && 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);
	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;
		*/
		if (sol != -1)
			break;
		else
			if (w[i+1].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;
}