Cod sursa(job #594078)

Utilizator nicknameLare Nicu nickname Data 6 iunie 2011 10:42:26
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct Sum{
	int x1,x2,x3,s;
}b[1000005];
int n1=0;

bool Cmp(Sum a,Sum b){
	return a.s < b.s;
}

int BS(int a){
	int s=0,e=n1;
	while (s <= e){
		int m=s+(e-s)/2;
		if (a == b[m].s)
			return m;
		else
			if (a > b[m].s)
				s=m+1;
			else
				e=m-1;
	}
	return -1;
}

int main(){
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	int a[105],s,n;
	scanf("%d",&n);
	scanf("%d",&s);
	for (int i=0; i<n; ++i)
		scanf("%d",a+i);
	for (int i=0; i<n; ++i)
		for (int j=i; j<n; ++j)
			for (int k=j; k<n; ++k){
				b[n1].x1=a[i];
				b[n1].x2=a[j];
				b[n1].x3=a[k];
				b[n1++].s=a[i]+a[j]+a[k];
			}
	sort(b,b+n1-1,Cmp);
	for (int i=0; i<n1; ++i){
		if (b[i].s < s){
			int k=BS(s-b[i].s);
			if (k >= 0){
				printf("%d %d %d %d %d %d",b[i].x1,b[i].x2,b[i].x3,b[k].x1,b[k].x2,b[k].x3);
				return 0;
			}
		}
	}
	printf("-1");
	return 0;
}