Pagini recente » Cod sursa (job #2092762) | Cod sursa (job #2884901) | Cod sursa (job #3038382) | Cod sursa (job #224605) | Cod sursa (job #3131901)
#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;
}