Cod sursa(job #173432)

Utilizator Mishu91Andrei Misarca Mishu91 Data 7 aprilie 2008 19:28:45
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 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 x,y,z,s;}lot;

lot B[Nmax*Nmax*Nmax]; 

struct cmp{    
              bool operator () (const lot &a, const lot &b) const    
              {    
                   if (a.s < b.s) return 1;   
                   return 0;    
              }    
          };    


int main()
{
  freopen(IN,"r",stdin);
  freopen(OUT,"w",stdout);
  
  int i,j,k;
  
  scanf ("%ld %ld", &N, &S);  
  for (i = 1; i <= N; ++i)  
      scanf ("%ld", a + i);  
      
  int nd = 0;  
  for (i = 1; i <= N; ++i)  
    for (j = 1; j <= N; ++j)  
        for (k = 1; k <= N; ++k)  
        {  
            ++nd;  
            B[nd].s = a[i] + a[j] + a[k], B[nd].x = a[i], B[nd].y = a[j], B[nd].z = a[k];  
        }  
  
  sort (B + 1, B + nd + 1, cmp());  
  
  for (i = 1; i <= nd; ++i)  
      if (B[i].s <= S - B[i].s)  
    {  
               int li = i; int lf = nd;  
               int m;  
               while (li <= lf)  
               {  
                     m = (li + lf) >> 1;  
                     if (B[m].s == S - B[i].s) break;  
                     if (B[m].s < S - B[i].s) li = m + 1;  
                        else lf = m - 1;  
               }  
                 
               if (B[m].s == S - B[i].s)   
               {  
                          printf ("%ld %ld %ld %ld %ld %ld", B[m].x, B[m].y, B[m].z, B[i].x, B[i].y, B[i].z);  
                          return 0;  
               }  
    }  
  printf ("-1\n");  
  return 0;
}