Cod sursa(job #173436)

Utilizator Mishu91Andrei Misarca Mishu91 Data 7 aprilie 2008 19:32:04
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>  
#include <algorithm>  
#include <vector>  
#define IN "loto.in"  
#define OUT "loto.out"  
#define Nmax 102  
  
using namespace std;  
  
long N,S,a[Nmax];  
  
typedef struct   
{long a,b,c,s;}lot;  
  
lot v[Nmax*Nmax*Nmax];   
  
void citire()  
{  
  scanf("%ld %ld",&N,&S);  
    
  for(int i=0; i<N; i++)  
    scanf("%ld",a+i);  
}  
  

struct comp
{
  bool operator() (const lot &a, const lot &b) const
  {
    return (a.s < b.s);
  }
}  ;
  
int nr;  
  
int main()  
{  
  freopen(IN,"r",stdin);  
  freopen(OUT,"w",stdout);  
  citire();  
    
    
  lot t;  
  for(int i=0; i<N; i++)  
    for(int j=0; j<N; j++)  
      for(int k=0; k<N; k++)  
      {  
        v[nr].s = a[i] + a[j] + a[k];  
        v[nr].a = a[i], v[nr].b = a[j], v[nr++].c = a[k];    
      }  
        
  sort(v,v+nr,comp());  
    
    
  for(int i=0; i< nr; i++)  
  {  
    if(v[i].s + v[i].s > S) continue;  
      
    int li = i, lf = nr-1,m;  
      
    while(li <= lf)  
    {  
      m = (li+lf) >> 1;  
        
      if(v[m].s + v[i].s == S)  
      {  
        printf("%ld %ld %ld %ld %ld %ld\n",v[i].a,v[i].b,v[i].c,v[m].a,v[m].b,v[m].c);  
        return 0;  
      }  
        
      if(v[m].s + v[i].s > S)  
        lf = m-1;  
        
      else  
        li = m+1;  
    }  
  }  
    
  printf("-1\n");  
  return 0;  
}