Cod sursa(job #3131979)

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

using namespace std;

vector<int> genereaza(const vector<int>& num, const vector<int>& num_selectate, int suma_finala, int suma_curenta, int start) {
    if (num_selectate.size() == 6) {
        if (suma_curenta == suma_finala) {
            return num_selectate;
        } else {
            return vector<int>();
        }
    }

    for (int i = start; i < num.size(); i++) {
        int new_sum = suma_curenta + num[i];
        if (new_sum <= suma_finala) {
            vector<int> selectate_update = num_selectate;
            selectate_update.push_back(num[i]);
            vector<int> result = genereaza(num, selectate_update, suma_finala, new_sum, i);
            if (!result.empty()) {
                return result;
            }
        }
    }

    return vector<int>();
}

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

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

    // CITIREA
    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
    vector<int> castigator = gaseste_finale(N, S, num_loterie);

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

    return 0;
}