Cod sursa(job #1428282)

Utilizator greenadexIulia Harasim greenadex Data 3 mai 2015 23:38:41
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int N, S, ok, sum;
vector <int> numbers, sums;

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

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)
                    sums.push_back(sum);
            }

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

    for (auto it : sums)
        if (bin_search(0, N - 1, S - it) != -1) {
            ok = 1;
            sum = it;
            break;
        }

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