Cod sursa(job #283114)

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

#define MAXN 101
#define MAXTrip 1100000

using namespace std;

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

comp com[MAXTrip];

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

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

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


int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    
    scanf("%d %d",&N,&S);
    
    for( i = 1 ; i <= N ; i++)
     scanf("%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++)
      {
          com[++contor].suma = v[i]+v[j]+v[k];
          com[contor].term1  = v[i];
          com[contor].term2  = v[j];
          com[contor].term3  = v[k];
      } 
   sort(com+1,com+contor+1, cmp);
  
  i = 1;
  j = contor;
  while(i <= j)
          {
          if(com[i].suma + com[j].suma == S)
                         {
                         printf("%d %d %d %d %d %d\n", com[i].term1,com[i].term2,com[i].term3,com[j].term1,com[j].term2,com[j].term3);
                         return 0;
                         }
          else
              while(com[i].suma + com[j].suma > S)
                                j--;
          if(com[i].suma + com[j].suma == S)
                         {
                         printf("%d %d %d %d %d %d\n", com[i].term1,com[i].term2,com[i].term3,com[j].term1,com[j].term2,com[j].term3);
                         return 0;
                         }
          i++;
          }
          
printf("-1");  
  
return 0;
}