Pagini recente » Cod sursa (job #431826) | Cod sursa (job #2541634) | Cod sursa (job #550216) | Cod sursa (job #515889) | Cod sursa (job #2915685)
#include <fstream>
#include <vector>
using namespace std;
ofstream fout("loto.out");
vector<int> sol, v;
long long ts = 0, s;
int n, cmax = 0;
void print_sol() {
for (int i = 0; i < 5 ; i++)
fout << sol[i] << " ";
fout << sol[sol.size() - 1];
fout.close();
exit(0);
}
bool found_sol() {
return ts == s && sol.size() == 6;
}
void backtrack() {
ts -= sol[sol.size() - 1];
sol.pop_back();
}
void btk(int idx) {
if (found_sol())
print_sol();
if (sol.size() >= 6)
return;
for (int i = idx; i < n ; i++) {
if (ts + v[i] <= s && sol.size() < 6) {
if (sol.size() == 4 && cmax < s - ts - v[i])
continue;
sol.push_back(v[i]);
ts += v[i];
btk(i);
backtrack();
}
}
}
vector<int> qsort(vector<int> vv) {
int piv = vv.size() / 2;
vector<int> l;
vector<int> h;
if (vv.size() == 1)
return vv;
for (int e : vv) {
if (e < vv[piv])
l.push_back(e);
else
h.push_back(e);
}
vector<int> buf = qsort(l);
for (int e: qsort(h))
buf.push_back(e);
return buf;
}
int main() {
ifstream fin("loto.in");
fin >> n;
fin >> s;
int tmp;
for (int i = 0 ; i < n; i++) {
fin >> tmp;
if (tmp > cmax)
cmax = tmp;
v.push_back(tmp);
}
fin.close();
v = qsort(v);
btk(0);
fout << -1;
fout.close();
return 0;
}