Pagini recente » Cod sursa (job #979261) | Cod sursa (job #527313) | Cod sursa (job #1193704) | Cod sursa (job #43371) | Cod sursa (job #1424327)
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
typedef vector<int> container;
bool find_loto(container& v, int numbers, int S, int pos, container& sol)
{
if (S == 0 && numbers != 0) return false;
if (S > 0 && numbers <= 0) return false;
if (S < 0) return false;
if (S == 0 && numbers == 0) return true;
bool found = false;
int pos2 = pos;
while (!found && pos2 >= 0)
{
///find the first id between pos and 0 such that v[pos2] <= S
while (pos2 >= 0 && v[pos2] > S) pos2--;
if (pos2 < 0) return false;
//perform binary search instead of while
// if (v[pos2] > S)
// {
// int a = 0, b = pos2;
// while (a < b)
// {
// int m = (a + b) / 2;
// if (v[m] > S) b = m - 1;
// else a = m;
// }
//
// if (a != b) return false;
// else pos2 = b;
// }
found = find_loto(v, numbers - 1, S - v[pos2], pos2, sol);
if (found) sol.push_back(v[pos2]);
else pos2--;
}
return found;
}
//int loto()
int main()
{
string in_file = "loto.in";
string out_file = "loto.out";
const int MAX_N = 100;
int N, S;
container v;
//read data from file
ifstream ifs;
ifs.open(in_file.c_str());
ifs >> N >> S;
v.resize(N);
for (int i = 0; i < N; i++) ifs >> v[i];
ifs.close();
//data available, now win the lottery
std::sort(v.begin(), v.end());
container sol;
bool found = find_loto(v, 6, S, N-1, sol);
ofstream ofs;
ofs.open(out_file.c_str());
if (!found) ofs << -1;
else for (auto& a : sol) ofs << a << " ";
ofs.close();
}