Pagini recente » Cod sursa (job #2532683) | Cod sursa (job #734384) | Cod sursa (job #159732) | Cod sursa (job #2280904) | Cod sursa (job #1067268)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;
vector<int> numbers;
int n, s, v[10];
int it = 0;
int maxno;
int sofar;
int choice[10];
void write_sol_and_quit() {
ofstream out("loto.out");
for (int i = 1; i <= 6; ++i) {
out << (i == 1 ? "" : " ") << v[i];
}
out << std::endl;
out.close();
exit(0);
}
void gen(int current_level) {
// If you've run out of space, test for solutions.
if (current_level == 7) {
if (sofar == s) {
write_sol_and_quit();
} else {
return;
}
}
while (choice[current_level] < numbers.size()) {
int current_no = numbers[choice[current_level]];
// Will we underrun with the current choice?
if (sofar + current_no + (6 - current_level) * maxno < s) {
choice[current_level]++;
continue;
}
// Will we overrun with the current choice? Stop and backtrack.
if (sofar + (6 - current_level + 1) * current_no > s) {
return;
}
// Assume the current choice, and then give it up.
v[current_level] = current_no;
sofar += current_no;
choice[current_level + 1] = choice[current_level];
gen(current_level + 1);
sofar -= current_no;
// Advance the choice.
choice[current_level]++;
}
}
int main()
{
ifstream in("loto.in");
in >> n >> s;
for (int i = 0; i < n; ++i) {
int x;
in >> x;
numbers.push_back(x);
}
std::sort(numbers.begin(), numbers.end());
maxno = numbers[numbers.size() - 1];
choice[1] = 0;
gen(1);
// If it returned, that's bad news.
ofstream out("loto.out");
out << "-1\n";
out.close();
// std::cerr << "Iterations: " << it << std::endl;
return 0;
}