Cod sursa(job #1428449)

Utilizator greenadexIulia Harasim greenadex Data 4 mai 2015 16:26:31
Problema Loto Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int N, S, out;
vector <int> numbers, sums;

int bin_search(int l, int r, int nr) {
    while (l <= r) {
        int mid = (r - l) / 2 + l;
        if (sums[mid] == nr)
            return 1;
        else if (sums[mid] < nr)
            l = mid + 1;
        else r = mid - 1;
    }
    return 0;
}

void afis (int sum) {
    for (auto x : numbers)
        for (auto y : numbers)
            for (auto z : numbers)
                if (x + y + z == sum) {
                    fout << x << ' ' << y << ' ' <<  z;
                    return;
                }
}

int main() {
    fin >> N >> S;
    for (int i = 1, nr; i <= N; i++) {
        fin >> nr;
        numbers.push_back(nr);
    }

    for (auto x : numbers)
        for (auto y : numbers)
            for (auto z : numbers) {
                int sum = x + y + z;
                if (sum <= S && !bin_search(0, sums.size() - 1, sum))
                    sums.push_back(sum);
            }

    sort(sums.begin(), sums.end());

    for (auto sum : sums)
        if (bin_search(0, sums.size() - 1, S - sum)) {
            out = sum;
            break;
        }

    if (!out) {
        fout << -1;
        return 0;
    } else {
        afis(out);
        fout << ' ';
        afis(S - out);
    }
    return 0;
}