Cod sursa(job #2891073)

Utilizator AndreiAncutaAndrei Ancuta AndreiAncuta Data 17 aprilie 2022 14:19:29
Problema Loto Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 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");

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

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

    ofs << "-1\n";

    ofs.close();

    return 0;
}