Cod sursa(job #642589)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 1 decembrie 2011 19:25:00
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <algorithm>
#include <cstdlib>

using namespace std;

#define file_in "loto.in"
#define file_out "loto.out"

struct loto{
	int suma;
	int i;
	int j;
	int k;
};

loto q[101*101*101];
int N,nr,i,j,k,S;
int V[111],X;

int cmp(loto a, loto b){
	
	return (a.suma<b.suma);
}

int main(){
	
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &N, &S);
	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){
				   q[++nr].suma=V[i]+V[j]+V[k];
				   q[nr].i=i;
				   q[nr].j=j;
				   q[nr].k=k;
			  }
			  
	sort(q+1,q+nr+1,cmp);

    for (i=1;i<=N;++i)
         for (j=1;j<=N;++j)
              for (k=1;k<=N;++k) {
				  X=S-V[i]-V[j]-V[k];
				  
				  int ls=1;
				  int ld=nr;
				  int  mij;
				  while(ls<=ld){
					  mij=(ld+ls)/2;
						if (q[mij].suma>X)
							ld=mij-1;
						else
							ls=mij+1;
				  }
				  mij=(ls+ld)/2;
				  if (q[mij].suma>X) mij--;
				  if (q[mij].suma==X)
					  //if (q[mij].suma==X)
				  {
						  printf("%d %d %d %d %d %d\n", V[q[mij].i],V[q[mij].j],V[q[mij].k],V[i],V[j],V[k]);
						  exit(0);
					  }
			  }
	printf("-1\n");		  
	return 0;
}