Pagini recente » Cod sursa (job #2650655) | Cod sursa (job #3207163) | Cod sursa (job #1901789) | Cod sursa (job #3286666) | Cod sursa (job #466758)
Cod sursa(job #466758)
#include <stdio.h>
#include <vector>
using namespace std;
vector <long int> v;
long int sume[300001], alege[300001], sume_aux[300001], nr[300001];
long int suma_totala;
long int P, i, j, k;
void afisare (long int S)
{
FILE *g = fopen ("congr.out","w");
k = S;
while (alege[k])
{
fprintf (g,"%ld ", alege[k]);
k -= v[alege[k]];
}
fclose(g);
}
int main ()
{
FILE *f = fopen ("congr.in","r");
fscanf (f,"%ld", &P);
P *= 2;
P --;
v.push_back (0);
for (i=1; i<=P; ++i)
{
fscanf (f,"%d", &j);
v.push_back (j);
suma_totala += v.back();
}
for (i=1; i<=P; ++i)
{
sume_aux[v[i]] = 1;
//printf ("%d\n", v[i]);
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;
//printf ("%d\n\n", nr[j]);
}
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);
fclose(f);
return 0;
}
}
/*for (i=1; i<=suma_totala; ++i)
printf ("%d : %d din %d numere\n", i, sume[i], nr[i]);*/
return 0;
}