Cod sursa(job #398369)

Utilizator andreea1coolBobu Andreea andreea1cool Data 18 februarie 2010 16:21:52
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct adun{
       long int a,b,c,s;
       };
int cmp(adun a,adun b){
	return a.s<b.s;
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    long int n,s,k,i,j,nr[101],l=1,s1,gasit=0,p,poz;
    adun v[500000],a,b;
    scanf("%ld%ld",&n,&s);
    for(i=1;i<=n;i++){
		scanf("%ld",&nr[i]);
	}
	for(i=1;i<=n;i++){
		for(j=i;j<=n;j++){
			for(k=j;k<=n;k++){
				v[l].a=nr[i];
				v[l].b=nr[j];
				v[l].c=nr[k];
				v[l].s=nr[i]+nr[j]+nr[k];
				l++;
			}
		}
	}
	sort(v+1,v+l,cmp);
	for(p=1;p*2<=l-1;p*=2);
	
	for(i=1;i<=l-1;i++){
		k=p;
		b=v[i];
		s1=s-b.s;
		for(poz=0;k;k=k/2){
			if(poz+k<=l-1)
			if(v[k+poz].s<=s1){
				poz=poz+k;
			}
		}
			if(v[poz].s==s1){
				gasit=1;
				a=v[poz];
				break;
			}
	}


if(gasit==1){
	printf("%ld %ld %ld %ld %ld %ld",b.a,b.b,b.c,a.a,a.b,a.c);
}else{
	printf("-1");
}
return 0;
}