Cod sursa(job #466628)

Utilizator miculprogramatorA Cosmina - vechi miculprogramator Data 27 iunie 2010 12:22:07
Problema Congr Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 1.49 kb
#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;
}