Pagini recente » Cod sursa (job #2694365) | Cod sursa (job #2631530) | Cod sursa (job #368619) | Cod sursa (job #1878770) | Cod sursa (job #2915796)
#include <fstream>
#include <vector>
using namespace std;
ofstream fout("loto.out");
vector<int> sol, v;
long long ts = 0, s;
int n;
vector<int> qsort(vector<int> v, int ll, int hh) {
if (hh - ll < 1)
return v;
int p = -1, l = ll, h = hh;
int piv = v[l + (h - l) / 2];
while (l < h) {
while (v[l] < piv)
l++;
while (v[h] > piv)
h--;
if (l >= h) {
p = h;
break;
}
int tmp = v[l];
v[l] = v[h];
v[h] = tmp;
l++;
h--;
}
if (p == -1)
p = h;
v = qsort(v, ll, p);
v = qsort(v, p + 1, hh);
return v;
}
void print_sol() {
sol = qsort(sol, 0, 5);
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 l, int h) {
if (found_sol())
print_sol();
if (sol.size() >= 6)
return;
while(l <= h) {
int m = l + (h - l) / 2;
int csum = ts + v[m];
int rest = 5 - (int)sol.size();
if (csum + v[n - 1] * rest < s) {
l = m + 1;
continue;
}
if (csum + v[0] * rest > s) {
h = m - 1;
continue;
}
if (csum <= s) {
sol.push_back(v[m]);
ts += v[m];
btk(0, n - 1);
backtrack();
l = m + 1;
} else
h = m - 1;
}
}
int main() {
ifstream fin("loto.in");
fin >> n;
fin >> s;
int tmp;
for (int i = 0 ; i < n; i++) {
fin >> tmp;
v.push_back(tmp);
}
fin.close();
v = qsort(v, 0, n - 1);
btk(0, n - 1);
fout << -1;
fout.close();
return 0;
}