Cod sursa(job #372596)

Utilizator vladiiIonescu Vlad vladii Data 10 decembrie 2009 21:53:48
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <iostream>
#include <fstream>
using namespace std;
fstream f2;
int n, elem[101], s[1000001];
int refasume(int a) {
     int i, j, x;
     for(i=1; i<=n; i++) {
         for(j=1; j<=n; j++) {
              for(x=1; x<=n; x++) {
                   if(elem[i]+elem[j]+elem[x]==a) {
                        f2<<elem[i]<<" "<<elem[j]<<" "<<elem[x]<<" ";
                        return 0;
                   }
              }
         }
     }
}
                        
int main() {
    fstream f1;
    int sum, nr=0, i, j, k, p, li, ls;
    f1.open("loto.in", ios::in);
    f2.open("loto.out", ios::out);
    f1>>n>>sum;
    for(i=1; i<=n; i++) {
         f1>>elem[i];
    }
    f1.close();
    for(i=1; i<=n; i++) {
         for(j=1; j<=n; j++) {
              for(k=1; k<=n; k++) {
                   s[nr]=elem[i]+elem[j]+elem[k];
                   nr++;
              }
         }
    }
    sort(s, s+nr);
    for(k=0; k<nr; k++) {
         //iau s[k] si fac cautare binara dupa sum-s[k]
         li=0; ls=nr-1;
         while(li<=ls) {
              p=li+(ls-li)/2;
              if(s[p]==sum-s[k]) {
                   //am gasit
                   //refac sumele
                   refasume(s[p]);
                   refasume(sum-s[p]);
                   f2.close();
                   return 0;
              }
              else if(s[p]<sum-s[k]) {
                   //caut in dreapta
                   li=p+1;
              }
              else {
                   //caut in stinga
                   ls=p-1;
              }
         }
    }
    f2<<-1<<endl;
    f2.close();
    return 0;
}