Cod sursa(job #2891066)

Utilizator AndreiAncutaAndrei Ancuta AndreiAncuta Data 17 aprilie 2022 14:05:09
Problema Loto Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <unordered_map>
#include <vector>

int main() {
    std::ifstream ifs("loto.in");

    unsigned n, s;
    ifs >> n >> s;

    std::vector<unsigned> nums;
    nums.resize(n);

    for (unsigned i = 0; i < n; i++) {
        ifs >> nums[i];
    }

    ifs.close();

    struct Triplet {
        unsigned first, second, third;
    };

    std::unordered_map<unsigned, Triplet> sums;

    for (unsigned i1 = 0; i1 < n; i1++) {
        for (unsigned i2 = i1; i2 < n; i2++) {
            for (unsigned i3 = i2; i3 < n; i3++) {
                unsigned sum = nums[i1] + nums[i2] + nums[i3];
                sums[sum] = {nums[i1], nums[i2], nums[i3]};
            }
        }
    }

    std::ofstream ofs("loto.out");

    unsigned sum = 0;
    for (unsigned i1 = 0; i1 < n; i1++) {
        sum += nums[i1];
        for (unsigned i2 = 0; i2 < n; i2++) {
            sum += nums[i2];
            for (unsigned i3 = 0; i3 < n; i3++) {
                sum += nums[i3];

                // Search for sum complement
                auto it = sums.find(s - sum);
                if (it != sums.end()) {
                    auto triplet = it->second;
                    // Found a solution
                    ofs << nums[i1] << ' ' << nums[i2] << ' ' << nums[i3] << ' '
                        << triplet.first << ' ' << triplet.second << ' '
                        << triplet.third << '\n';
                    return 0;
                }

                sum -= nums[i3];
            }
            sum -= nums[i2];
        }
        sum -= nums[i1];
    }

    ofs << "-1\n";

    ofs.close();

    return 0;
}