Mai intai trebuie sa te autentifici.
Cod sursa(job #1053010)
Utilizator | Data | 12 decembrie 2013 00:44:44 | |
---|---|---|---|
Problema | Loto | Scor | 5 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.81 kb |
#include <algorithm>
#include <iostream>
using namespace std;
struct suma
{
int val, a, b, p;
};
bool bin_cprer(suma, suma);
bool cprer(suma, suma);
int binFindPos = -1;
int main()
{
int n, s;
int *nr;
suma *sume;
freopen("loto.in", "r", stdin);
freopen("loto.out", "w", stdout);
cin >> n >> s;
nr = new int[n];
sume = new suma[n*(n - 1) / 2 + n];
for (int i = 0; i < n; ++i)
{
cin >> nr[i];
}
int ctr = 0;
for (int i = 0; i < n; ++i)
{
for (int j = i; j < n; ++j)
{
sume[ctr].a = i;
sume[ctr].b = j;
sume[ctr].val = nr[i] + nr[j];
sume[ctr].p = ctr;
++ctr;
}
}
sort(sume, sume + ctr, cprer);
bool found = false;
int result[6];
for (int i = 0; i < ctr; ++i)
{
if (s - sume[i].val < 0)
break;
for (int j = i; j < ctr; ++j)
{
suma csum;
csum.val = s - sume[i].val - sume[j].val;
if (csum.val < 0)
{
break;
}
if (binary_search(sume, sume + ctr, csum, bin_cprer))
{
result[0] = nr[sume[i].a];
result[1] = nr[sume[i].b];
result[2] = nr[sume[j].a];
result[3] = nr[sume[j].b];
result[4] = nr[sume[binFindPos].a];
result[5] = nr[sume[binFindPos].b];
found = true;
/*for (int k = 0; k < j; k++)
{
if (sume[k].val == csum.val)
{
result[4] = nr[sume[k].a];
result[5] = nr[sume[k].b];
break;
}
}*/
}
if (found) break;
}
if (found) break;
}
if (found)
{
sort(result, result + 6);
for (int i = 0; i < 6; ++i)
{
cout << result[i] << " ";
}
}
else cout << "-1";
}
bool bin_cprer(suma a, suma b)
{
if (a.val == b.val)
{
if (a.p >= 0)
binFindPos = a.p;
}
return a.val < b.val;
}
bool cprer(suma a, suma b)
{
if (a.val < b.val)
{
return true;
}
else return false;
}