Cod sursa(job #3128591)

Utilizator florinilie324Ilie Florin Alexandru florinilie324 Data 10 mai 2023 07:49:28
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
using namespace std;

bool gaseste_combinatie(const vector<int> &numere, int N, int S, vector<int> &rezultat) {
    unordered_map<int, vector<int>> sume_partiale;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int suma = numere[i] + numere[j];

            if (sume_partiale.find(S - suma) != sume_partiale.end()) {
                rezultat = {numere[i], numere[j]};
                rezultat.insert(rezultat.end(), sume_partiale[S - suma].begin(), sume_partiale[S - suma].end());
                return true;
            }

            for (int k = 0; k < N; k++) {
                int suma_curenta = numere[k] + suma;

                if (sume_partiale.find(suma_curenta) == sume_partiale.end()) {
                    sume_partiale[suma_curenta] = {numere[i], numere[j], numere[k]};
                }
            }
        }
    }

    return false;
}

int main() {
    int N, S;
    ifstream fin("loto.in");
    ofstream fout("loto.out");
    fin >> N >> S;
    vector<int> numere(N);
    for (int i = 0; i < N; i++) {
        fin >> numere[i];
    }
    fin.close();

    vector<int> rezultat;
    if (gaseste_combinatie(numere, N, S, rezultat)) {
        for (int numar : rezultat) {
            fout << numar << " ";
        }

    } else {
        fout << -1;
    }

    fout.close();
    return 0;
}