Cod sursa(job #743005)

Utilizator vendettaSalajan Razvan vendetta Data 2 mai 2012 19:11:55
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#include <algorithm>

#define nmax 105
#define combmax 1000005

using namespace std;

ifstream f("loto.in");
ofstream g("loto.out");

int n, s, a[nmax], cnt, poz;
typedef struct{

    int a, b, c, nr;

}camp;

camp comb[combmax];

void citeste(){

    f >> n >> s;
    for(int i=1; i<=n; i++) f >> a[i];

}

bool cmp(camp a, camp b){

    return a.nr < b.nr;

}


void prec(){

    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            for(int k=j; k<=n; k++){
                int sum = a[i] + a[j] + a[k];
                camp val;
                val.a = a[i]; val.b = a[j];
                val.c = a[k]; val.nr = sum;
                comb[++cnt] = val;
            }
        }
    }

    sort(comb+1, comb+cnt+1, cmp);

}

bool cb(int x){

    int st = 1;
    int dr = cnt;

    while (st <= dr){
        int mij = (st + dr) / 2;
        if (comb[mij].nr == x){
            poz = mij;
            return 1;
        }else if(comb[mij].nr < x ){
            st = mij + 1;
        }else if(comb[mij].nr > x ){
            dr = mij - 1;
        }
    }

    return 0;

}

void rezolva(){

    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            for(int k=j; k<=n; k++){
                int sum = s - (a[i] + a[j] + a[k]);
                poz = 0;
                if (cb(sum)){
                    g << a[i] << " " << a[j] << " " << a[k] << " " << comb[poz].a << " " << comb[poz].b << " " << comb[poz].c << "\n";
                    return;
                }
            }
        }
    }

    g << -1 << "\n";

}

int main(){

    citeste();
    prec();
    rezolva();

    f.close();
    g.close();

    return 0;

}