Cod sursa(job #2186049)

Utilizator GarboteialexGarbotei Alex Garboteialex Data 25 martie 2018 12:07:35
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

int n, S, l;
int v[101];
int sumtrei[1000005];
int sol[7];

int bin(int val) {
    int lo = 1, hi = l, mid;
    while(lo < hi) {
        mid = (lo + hi) / 2;
        if(sumtrei[mid] < val) {
            lo = mid + 1;
        }else {
            hi = mid;
        }
    }

    return lo;
}

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

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            for(int k = 1; k <= n; k++) {
                sumtrei[++l] = v[i] + v[j] + v[k];
            }
        }
    }

    sort(sumtrei + 1, sumtrei + 1 + l);
    
    int s1,s2;
    for(int i = 1; i <= l; i++) {
        int rb = bin(S - sumtrei[i]);
        if(sumtrei[i] + sumtrei[rb] == S) {
            s1 = sumtrei[i];
            s2 = sumtrei[rb];
            break;
        }
    }

    if(s1 + s2 == S) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                for(int k = 1; k <= n; k++) {
                    if(v[i] + v[j] + v[k] == s1) {
                        sol[1] = v[i];
                        sol[2] = v[j];
                        sol[3] = v[k];
                    }
                    if(v[i] + v[j] + v[k] == s2) {
                        sol[4] = v[i];
                        sol[5] = v[j];
                        sol[6] = v[k];
                    }
                }
            }
        }

        sort(sol + 1, sol + 7);
        for(int i = 1; i <= 6; i++) {
            fout << sol[i] << " ";
        }

    }else {
        fout << "-1";
    } 
 

}