Cod sursa(job #3056)

Utilizator RazvanSSavu Razvan RazvanS Data 20 decembrie 2006 16:53:51
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>

#define Nmax 200000
#define N 101

using namespace std;

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=i;
                   S[t].y=j;
                   S[t].z=k;
                 } 
     sort(1, t);
     ofstream fout("loto.out");
     for(i=1;i<=t;i++)
         {v=s-S[i].s;
          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.close();
                              return 0;
                            }
                else if(S[c].s>v) b=c-1;
                         else a=c+1;
             }
         }
     fout<<"-1\n";
     fout.close();
     
     
     
     return 0;
 }