Cod sursa(job #173421)

Utilizator Mishu91Andrei Misarca Mishu91 Data 7 aprilie 2008 19:19:30
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 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 
{int 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);
}

inline bool comp(lot a, lot b)
{
  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("%d %d %d %d %d %d\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;
}