Cod sursa(job #466628)
#include <stdio.h>
using namespace std;
int v[300001], sume[300001], nr[300001], alege[300001], sume_aux[300001];
long int suma_totala;
long int P, i, j, k;
void afisare (int S)
{
FILE *g = fopen ("congr.out","w");
k = S;
while (alege[k])
{
fprintf (g,"%d ", alege[k]);
k -= v[alege[k]];
}
}
int main ()
{
FILE *f = fopen ("congr.in","r");
fscanf (f,"%ld", &P);
P *= 2;
P --;
for (i=1; i<=P; ++i)
{
fscanf (f,"%d", &v[i]);
suma_totala += v[i];
}
for (i=1; i<=P; ++i)
{
sume_aux[v[i]] = 1;
for (j=1; j<=suma_totala; ++j)
if (sume[j] == 1)
sume_aux[j+v[i]] = 1;
for (j=1; j<=suma_totala; ++j)
if (sume_aux[j] == 1 && sume[j] == 0)
{
sume[j] = 1;
if (v[i] != j)
{
nr[j] = 1 + nr[j-v[i]];
alege[j] = i;
}
else
{
alege[j] = i;
nr[j] = 1;
}
sume_aux[j] = 0;
}
for (j=1; j<=suma_totala; ++j)
if (nr[j] == ((P + 1) / 2) && j % ((P + 1) / 2) == 0)
{
afisare (j);
return 0;
}
}
/*for (i=1; i<=suma_totala; ++i)
printf ("%d : %d din %d numere\n", i, sume[i], nr[i]);*/
return 0;
}