Cod sursa(job #3132028)

Utilizator cristiosmCristian Magureanu cristiosm Data 21 mai 2023 22:48:11
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

std::vector<int> genereaza(const std::vector<int>& num, std::vector<int>& num_selectate, int suma_finala, int suma_curenta, size_t start) {
    std::stack<std::pair<size_t, int>> stiva;
    stiva.push(std::make_pair(start, suma_curenta));

    while (!stiva.empty()) {
        size_t i = stiva.top().first;
        int suma = stiva.top().second;
        stiva.pop();

        if (num_selectate.size() == 6) {
            if (suma == suma_finala) {
                return num_selectate;
            } else {
                continue;
            }
        }

        for (; i < num.size(); i++) {
            int new_sum = suma + num[i];
            if (new_sum <= suma_finala) {
                num_selectate.push_back(num[i]);
                stiva.push(std::make_pair(i + 1, new_sum));
            }
        }
    }

    return std::vector<int>();
}

std::vector<int> gaseste_finale(int N, int S, const std::vector<int>& num_loterie) {
    std::vector<int> num_loterie_copy = num_loterie;
    std::sort(num_loterie_copy.begin(), num_loterie_copy.end());
    std::vector<int> result = genereaza(num_loterie_copy, num_loterie_copy, S, 0, 0);
    return result.empty() ? std::vector<int>{-1} : result;
}

int main() {
    int N, S;
    std::vector<int> num_loterie;

    // CITIREA
    std::ifstream input("loto.in");
    input >> N >> S;
    for (int i = 0; i < N; i++) {
        int num;
        input >> num;
        num_loterie.push_back(num);
    }
    input.close();

    // CALCULARE NUMERE CASTIGATOARE
    std::vector<int> castigator = gaseste_finale(N, S, num_loterie);

    // AFISARE
    std::ofstream output("loto.out");
    if (castigator[0] == -1) {
        output << "-1" << std::endl;
    } else {
        for (size_t i = 0; i < castigator.size(); i++) {
            output << castigator[i] << " ";
        }
        output << std::endl;
    }
    output.close();

    return 0;
}