Pagini recente » Cod sursa (job #2735950) | Monitorul de evaluare | Cod sursa (job #363599) | Cod sursa (job #2135836) | Cod sursa (job #1728946)
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N = 105, L = 1000005, PUT = 1 << 19;
int v[N], sume[L], n, s, ct = 0, m, caut, sol[5], fin[10];
void bkt ()
{
if (ct == 3)
{
sume[++m] = s;
return;
}
int i;
for (i = 1; i <= n; i++)
{
s += v[i];
ct++;
bkt ();
s -= v[i];
ct--;
}
}
int cautBin (int x)
{
int pas = PUT, sol = 0;
while (pas != 0)
{
if (pas + sol <= m && sume[pas + sol] <= x)
sol += pas;
pas >>= 1;
}
return sol;
}
bool reconst ()
{
if (ct == 3)
{
if (s == caut)
return true;
return false;
}
int i;
for (i = 1; i <= n; i++)
{
sol[++ct] = v[i];
s += v[i];
if (reconst())
return true;
s -= v[i];
ct--;
}
return false;
}
int main ()
{
FILE *in, *out;
in = fopen ("loto.in", "r");
out = fopen ("loto.out", "w");
int s2;
fscanf (in, "%d%d", &n, &s2);
int i;
for (i = 1; i <= n; i++)
fscanf (in, "%d", &v[i]);
bkt ();
i = 0;
sort (sume + 1, sume + m + 1);
int select = -1, gas;
ct = 0;
s = 0;
for (i = 1; i <= m; i++)
{
while (sume[i] == select && i < m)
i++;
select = sume[i];
gas = cautBin (s2 - select);
if (select + sume[gas] == s2)
{
caut = select;
reconst();
fin[1] = sol[1]; fin[2] = sol[2]; fin[3] = sol[3];
caut = sume[gas];
ct = 0;
s = 0;
reconst();
fin[4] = sol[1]; fin[5] = sol[2]; fin[6] = sol[3];
int j;
sort (fin + 1, fin + 7);
for (j = 1; j <= 6; j++)
fprintf (out, "%d ", fin[j]);
return 0;
}
}
fprintf (out, "-1");
return 0;
}