Cod sursa(job #283084)

Utilizator gabor_oliviu1991gaboru corupt gabor_oliviu1991 Data 18 martie 2009 18:15:18
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<stdio.h>
#include<algorithm>

#define MAXN 101
#define MAXTrip 400000

using namespace std;

typedef struct comp;
struct comp
{
       int term1;
       int term2;
       int term3;
}
;

comp com[MAXTrip];

int Triplets[MAXTrip],v[MAXN],i,j,k,N,S,contor,ind,ok, sol;

int bin(int val)
{
    int left=1, right=contor, mij;
    while(left<=right)
    {
     mij=(left+right)/2;
     if( val == Triplets[mij]) return mij;
      else if(val > Triplets[mij]) left = mij+1;
       else if(val < Triplets[mij]) right = mij-1;
     }  
  return 0;
}     


int main()
{
    FILE*in=fopen("loto.in","r");
    FILE*out=fopen("loto.out","w");
    fscanf(in,"%d %d",&N,&S);
    
    for( i = 1 ; i <= N ; i++)
     fscanf( in ,"%d", &v[i]);
     
   sort(v+1,v+N+1);
   
   for( i = 1 ; i <= N ; i++)
    for( j = 1 ; j <= N; j++)
     for( k = 1 ; k <= N ; k++)
      {
          Triplets[++contor]=v[i]+v[j]+v[k];
          com[contor].term1=v[i];
          com[contor].term2=v[j];
          com[contor].term3=v[k];
      } 

       sort(Triplets+1,Triplets+contor+1);
  
for ( i = 1 ; i <= contor ; i++)
{
     if(S-Triplets[i]>0)
     {
        sol = bin(S-Triplets[i]);
        if(sol)
        {
               fprintf(out,"%d %d %d %d %d %d ",com[i].term1,com[i].term2,com[i].term3,com[sol].term1,com[sol].term2,com[sol].term3);
               ok = 1;
               break;
        }
     }
}
if(ok != 1) fprintf(out,"-1",-1);  
  
return 0;
}