Pagini recente » Cod sursa (job #3189188) | Cod sursa (job #2390026) | Cod sursa (job #1324855) | Cod sursa (job #1146516) | Cod sursa (job #1067310)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;
vector<int> numbers;
int n, s;
int choice[10];
void write_sol_and_quit() {
ofstream out("loto.out");
for (int i = 1; i <= 6; ++i) {
out << (i == 1 ? "" : " ") << numbers[choice[i]];
}
out << std::endl;
out.close();
exit(0);
}
void gen() {
int sofar = 0;
int current_level = 1;
bool just_strepped[10] = { false };
choice[1] = -1;
just_strepped[1] = true;
do {
while (choice[current_level] + 1 < numbers.size()) {
// Make a new choice for the current level, and assume it.
if (!just_strepped[current_level]) {
sofar -= numbers[choice[current_level]];
}
choice[current_level]++;
sofar += numbers[choice[current_level]];
just_strepped[current_level] = false;
// Print state:
//for (int i = 1; i <= current_level; ++i) {
// std::cerr << (i == 1 ? "" : " ") << numbers[choice[i]];
//}
//std::cerr << std::endl << sofar << std::endl << std::endl;
// If this choice is going to overrun, give it up and backtrack.
if (sofar + (6 - current_level) * numbers[choice[current_level]] > s) {
sofar -= numbers[choice[current_level]];
break;
}
// If we're underruning, give up the choice and continue.
if (sofar + (6 - current_level) * numbers[numbers.size() - 1] < s) {
continue;
}
// Win or advance the level.
if (current_level == 6) {
if (sofar == s) {
write_sol_and_quit();
}
} else {
current_level++;
choice[current_level] = choice[current_level - 1] - 1;
just_strepped[current_level] = true;
}
}
// Ran out of choices, decrease the level anyway.
current_level--;
} while (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());
gen();
// If it returned, that's bad news.
ofstream out("loto.out");
out << "-1\n";
out.close();
return 0;
}