Cod sursa(job #3131901)

Utilizator LazarDanielGabrielLazar Daniel-Gabriel LazarDanielGabriel Data 21 mai 2023 21:13:29
Problema Loto Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");
vector<int> chosen_numbers;

bool generate_ticket(const vector<int>& numbers, int target_sum) {
    int n = numbers.size();
    vector<vector<bool>> dp(target_sum + 1, vector<bool>(n + 1, false));
    vector<vector<int>> prev(target_sum + 1, vector<int>(n + 1, -1));
    dp[0][0] = true;

    for (int i = 1; i <= target_sum; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i][j - 1];
            prev[i][j] = prev[i][j - 1];

            int num = numbers[j - 1];
            if (i >= num && dp[i - num][j - 1]) {
                dp[i][j] = true;
                prev[i][j] = j - 1;
            }
        }
    }

    if (!dp[target_sum][n]) {
        return false;
    }

    int current_sum = target_sum;
    int index = n;
    while (current_sum > 0 && index > 0) {
        if (prev[current_sum][index] != index - 1) {
            chosen_numbers.push_back(numbers[index - 1]);
            current_sum -= numbers[index - 1];
        }
        index--;
    }

    return true;
}

int main() {
    int N, S;
    fin >> N >> S;

    vector<int> numbers(N);
    for (int i = 0; i < N; i++) {
        fin >> numbers[i];
    }
    fin.close();

    if (generate_ticket(numbers, S)) {
        for (int i = 5; i >= 0; i--) {
            fout << chosen_numbers[i] << " ";
        }
        fout << "\n";
    } else {
        fout << "-1\n";
    }
    fout.close();

    return 0;
}