Pagini recente » Cod sursa (job #902744) | Cod sursa (job #1498341) | Cod sursa (job #1293207) | Cod sursa (job #1398907) | Cod sursa (job #1424328)
#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;
else a = m + 1;
}
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";
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();
}