Cod sursa(job #487560)

Utilizator cristian9Cristian Zloteanu cristian9 Data 25 septembrie 2010 16:23:59
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<cstdio>
#include<algorithm>
using namespace std;

struct numar{
	int a, b, c;
	long long s;
};

numar sum[1000000];
long long s, v[101];
int n, j, k, i, z, a, mini, maxi;

int cmp (numar x,numar y){
	return x.s < y.s ;
}

int cautare(long long balmus){
    mini=1;
    maxi=z;
    while(mini<=maxi){
        if(balmus==sum[(mini+maxi)/2].s){
            return (mini+maxi)/2;
        }
        else{
            if(a<sum[(mini+maxi)/2].s){
				maxi=(maxi+mini)/2-1;
			}
			else{
				mini=(mini+maxi)/2+1;
			}
        }
    }
    return 0;
}

int main(){
    freopen ("loto.in", "r", stdin);
    freopen ("loto.out", "w", stdout);

	scanf("%d %lld", &n, &s);

	for(i=1; i<=n; i++)
		scanf ("%ld ", &v[i]);

	for(i=1; i<=n; i++){
		for(j=1; j<=n; j++){
			for(k=1; k<=n; k++){
				sum[++z].s=v[i]+v[j]+v[k];
				sum[z].a=v[i];
				sum[z].b=v[j];
				sum[z].c=v[k];
			}
		}
	}

	sort(sum+1, sum+z+1, cmp);

	/*for(i=1; i<=z; i++){
		printf("%d %d %d %d\n", sum[i].s, sum[i].a, sum[i].b, sum[i].c);
	}
	return 0;
*/

	for(i=1; i<=z; i++){
		//printf("%d ", i);
		a=s-sum[i].s;
		//printf("%d ", a);
		if(0!=cautare(a)){
			printf("%d %d %d %d %d %d ", sum[i].a, sum[i].b, sum[i].c, sum[(mini+maxi)/2].a, sum[(mini+maxi)/2].b, sum[(mini+maxi)/2].c);
			return 0;
		}
	}

	printf("-1");
	return 0;
}