Cod sursa(job #777677)

Utilizator oana_popfmi - pop oana oana_pop Data 12 august 2012 23:34:49
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
int main()
{  ifstream f("loto.in");
   ofstream g("loto.out");
   
   int n, s, i, j, k, a, b, c, begin, end, mid, suma; 
   vector <int> val ,  sum;
   bool found=0;
   
   f>>n>>s;
   for(i=1; i<=n;i++)
   {   
       f>>k;
       val.push_back(k);
   }
       
   for(i=0 ; i<int(val.size());i++)
      for(j=0 ; j<int(val.size()); j++)
         for(k=0; k<int(val.size()); k++)
            sum.push_back(val[i]+val[j]+val[k]);
            
   sort(sum.begin(),sum.end());
   
   for(i=0 ; i<int(val.size());i++)
      for(j=0 ; j<int(val.size()); j++)
         for(k=0; k<int(val.size()); k++)
         if(!found){
           suma=val[i]+val[j]+val[k];
           
           begin=-1;
           end=int(sum.size());
           while(end-begin>1){
                              mid=begin+(end-begin)/2;
                              if ((suma+sum[mid])>s) end=mid;
                              else begin=mid;
                              }
           if (suma+sum[mid]==s){
               g<<val[i]<<" "<<val[j]<<" "<<val[k]<<"  ";
               
           for(a=0; a<int(val.size());a++)
              for(b=0; b<int(val.size()); b++)
                for(c=0; c<int(val.size()); c++)
                if(!found){
                   if(val[a]+val[b]+val[c]==s-suma){
                                                    g<<val[a]<<" "<<val[b]<<" "<<val[c];
                                                    found=1;
                                                    }
                   }
        found=1;   
      }
    }
    
    if(!found)  g<<"-1";
    return 0;
}