Cod sursa(job #2153060)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 5 martie 2018 22:20:29
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>
std::ifstream in("loto.in");
std::ofstream out("loto.out");
using namespace std;
 int n , S ;
  const int dimensiunea9a=101;
     int v[dimensiunea9a];
     inline void input()
     {
         in >> n >> S ;
          for( int i =1 ; i <=n ;++i)
                     in >> v[i];
     }

       struct element
       {
           int primu,al_doilea,al_treilea,suma;
       };
   element aux[4029005];
         int dim;
         inline void construiesc_ceva()
         {
             for(int i =1; i <=n ;++i)
                   for(int j =1 ; j <=n ;++j)
                            for(int k =1; k<=n ;++k)
             {
                 element e ;
                 e.primu=v[i];
                 e.al_doilea=v[j];
                 e.al_treilea=v[k];
                 e.suma=v[i]+v[j]+v[k];
                  aux[++dim]=e;
             }
         }
         inline bool compare(element i , element j)
         {
             return i.suma<j.suma;
         }

        int  caut_binar( int st, int dr, int x  )
{
     int mid;
     while ( st <= dr )
     {
          mid = ( st + dr ) / 2;
          if( aux[mid].suma == x ) return mid;
          if( aux[mid].suma < x ) st = mid +1; else dr = mid -1;

     }
     return -1;
}



int main()
{input();
construiesc_ceva();
sort(aux+1,aux+dim+1,compare);
//cout<<(sizeof(aux)+sizeof(v))/1024;

                for(int i =1 ; i <= dim ; ++i)
                {
                    int ce_am = aux[i].suma;
                          int pozitie = caut_binar(1,dim,S-ce_am);
                            if(pozitie!=-1)
                            {
                                out<<aux[i].primu<<" "<<aux[i].al_doilea<<" "<<aux[i].al_treilea<<" "<<aux[pozitie].primu<<" "<<aux[pozitie].al_doilea<<" "<<aux[pozitie].al_treilea;
                                return 0;
                            }
                }
                out<<"-1";
    return 0;
}