Cod sursa(job #2893756)

Utilizator 4N70N1U5Antonio Nitoi 4N70N1U5 Data 26 aprilie 2022 17:12:09
Problema Loto Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <vector>
#include <unordered_map>

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

template <class T>
struct triplet
{
    T first, second, third;
}; // Structura similara cu pair, dar pentru trei valori.

int main()
{
    int N, S;
    bool Exista = false;
    std::vector<int> Numere; // Numerele date in fisierul de intrare.
    std::unordered_map< int, triplet<int> > Sume;
    // In acest map voi stoca sumele ce se pot obtine din combinari de cate trei numere,
    // si care sunt numerele ce dau acea suma. Cheile vor fi sumele, iar valorile
    // tripletii formati din acele trei numere.

    fin >> N >> S;

    Numere.resize(N);

    for (int i = 0; i < N; i++)
        fin >> Numere[i];

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                if (Sume.find(Numere[i] + Numere[j] + Numere[k]) == Sume.end())
                {
                    triplet<int>* ElemSume = &Sume[Numere[i] + Numere[j] + Numere[k]];
                    ElemSume->first = Numere[i];
                    ElemSume->second = Numere[j];
                    ElemSume->third = Numere[k];
                    // Daca suma curenta nu este deja in map-ul de sume, atunci o adaug.
                }

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                if (Sume.find(S - (Numere[i] + Numere[j] + Numere[k])) != Sume.end() && !Exista)
                {
                    Exista = true;
                    triplet<int>* ElemSume = &Sume[S - (Numere[i] + Numere[j] + Numere[k])];
                    fout << Numere[i] << ' ';
                    fout << Numere[j] << ' ';
                    fout << Numere[k] << ' ';
                    fout << ElemSume->first << ' ';
                    fout << ElemSume->second << ' ';
                    fout << ElemSume->third;
                    return 0;
                    // Verific daca exista in map complementul sumei curente pentru a
                    // obtine suma S cautata. Daca exista, atunci afisez numerele gasite.
                }

    if (!Exista)
        fout << -1;

    return 0;
}