Cod sursa(job #1294913)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 18 decembrie 2014 14:32:58
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

struct str{
    int a; int b; int c; int s;
};

int cmp(str a, str b){
    return a.s < b.s;
}

str x[1000002];
int n, S[10], t, st, sum, L;
int v[101], dr, mid, i, j,k;

int main(){
    fin >> n >> L;
    for(i = 1; i <= n; i ++)
        fin >> v[i];

    for(i = 1; i <= n; i ++)
        for(j = i; j <= n; j ++)
            for(k = j; k <= n; k ++) {
                t ++;
                x[t].a = v[i];
                x[t].b = v[j];
                x[t].c = v[k];
                x[t].s = v[i] + v[j] + v[k];
            }

    sort(x + 1, x + t + 1, cmp);

    for(i = 1; i <= n; i++)
        for(j = i; j <= n; j++)
            for (k = j; k <= n; k++){
                sum = v[i] + v[j] + v[k];
                st = 1;
                dr = t;
                while(st <= dr){
                    mid = (st + dr) / 2;
                    if (L - sum == x[mid].s){
                        S[1] = x[mid].a;
                        S[2] = x[mid].b;
                        S[3] = x[mid].c;
                        S[4] = v[i];
                        S[5] = v[j];
                        S[6] = v[k];
                        sort(S + 1, S + 7);
                        for (i = 1; i <= 6; i++)
                            fout << S[i]<<" ";
                        return 0;
                    }
                    if(L - sum < x[mid].s)
                        dr = mid - 1;
                    else
                        st = mid + 1;
                }
            }
     fout << -1;
     return 0;
}