Cod sursa(job #160793)

Utilizator FlorinC1996Florin C FlorinC1996 Data 16 martie 2008 21:09:17
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
 #include <fstream>   
  
#define Nmax 200000   
#define N 101   
  
  
using namespace std;   
  
ofstream fout("loto.out");   
  
void out(int a)   
     {fout<<a<<'\n';   
     }   
  
  
struct sum3 {int s, x, y, z;} S[Nmax];   
  
  
void pahare(int p, int q)   
      {sum3 a;   
       a=S[p];   
       S[p]=S[q];   
       S[q]=a;   
      }    
  
  
int pivot(int p, int q)   
       {while(p<q)   
           {while(S[p].s<=S[q].s && p!=q)   
                p++;   
            if(p<q) pahare(p,q);   
            while(S[p].s<=S[q].s && p!=q)    
                q--;   
            if(p<q)  pahare(p, q);   
           }   
               
        return p;   
       }                       
  
  
void sort(int p, int q)   
       {if(q>p) {int k=pivot(p, q);   
                 sort(p, k-1);   
                 sort(k+1, q);   
                }   
       }              
          
  
  
int main(void)   
    {int A[N], n, s;   
     ifstream fin("loto.in");   
     fin>>n>>s;   
     int i, v, a, b, c;   
     for(i=1;i<=n;++i)   
        fin>>A[i];   
     fin.close();   
     int j, k, t=0;   
     for(i=1; i<= n;++i)   
          for(j=i; j<=n; j++)   
              for(k=j; k<=n; k++)   
                 { S[++t].s=A[i]+A[j]+A[k];   
                   S[t].x=A[i];   
                   S[t].y=A[j];   
                   S[t].z=A[k];   
                 }    
     sort(1, t);   
        
     for(i=1;i<=t;i++)   
         {v=s-S[i].s;//out (v);   
          a=i; b=t;   
          while(a<=b)   
             {c=(a+b)/2;   
              if(S[c].s==v) { fout<<S[i].x<<" "<<S[i].y<<" "<<S[i].z<<" "<<S[c].x<<" "<<S[c].y<<" "<<S[c].z<<'\n';   
                              //fout<<i<<" "<<c;    
                              fout.close();   
                              return 0;   
                            }   
                else if(S[c].s>v) b=c-1;   
                         else a=c+1;   
             }   
         }   
     fout<<"-1\n";   
     fout.close();   
        
        
        
     return 0;   
 }