Cod sursa(job #1428467)

Utilizator greenadexIulia Harasim greenadex Data 4 mai 2015 16:44:47
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct trio{
    int a, b, c;
};

bool compare (const pair <int, trio> x, const pair <int, trio> y){
    return x.first <= y.first;
}

int N, S;
vector <int> numbers;
vector <pair<int, trio>> sums;

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

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) == -1){
                    trio pack;
                    pack.a = x; pack.b = y; pack.c = z;
                    sums.push_back(make_pair(sum, pack));
                }
            }

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

    for (auto sum : sums)
        if (bin_search(0, sums.size() - 1, S - sum.first) != -1) {
            int i = bin_search(0, sums.size() - 1, S - sum.first);
            fout << sum.second.a << ' ' << sum.second.b << ' ' << sum.second.c << ' '
                 << sums[i].second.a << ' ' << sums[i].second.b << ' ' << sums[i].second.c;
            return 0;
        }
    fout << -1;
    return 0;
}