Pagini recente » Cod sursa (job #1655340) | Cod sursa (job #2834412) | Cod sursa (job #304758) | Cod sursa (job #2758269) | Cod sursa (job #3132028)
#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;
}