Cod sursa(job #487554)

Utilizator cristian9Cristian Zloteanu cristian9 Data 25 septembrie 2010 15:46:42
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
long n, s, v[101], j, k, i, z=0, a, mini, maxi;

struct numar{
	long a, b, c, s;
};
numar sum[1000000];

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

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

	scanf("%ld %ld", &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);
		mini=1;
		maxi=z;
		while(mini<=maxi){
			if(a==sum[(mini+maxi)/2].s){
				printf("%ld %ld %ld %ld %ld %ld ", 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;
			}
			else{
				if(a<sum[(mini+maxi)/2].s){
					maxi=(maxi+mini)/2-1;
				}
				else{
					mini=(mini+maxi)/2+1;
				}
			}
		}
	}

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