Cod sursa(job #466742)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 27 iunie 2010 13:57:32
Problema Congr Scor 0
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 1.3 kb
#include <stdio.h>
#define NMAX 600005
#define PMAX 305
int n,A[NMAX],B[PMAX][PMAX][PMAX],use[PMAX][PMAX][PMAX];
void read()
{
    scanf("%d",&n);
    int i;
    for (i=1; i<2*n; i++)
    {
        scanf("%d",&A[i]);
        if (A[i]>=n)
            A[i]%=n;
    }
}
void solve1()
{
    int i,j,k,rest;
    B[0][0][0]=1;
    for (i=1; i<2*n; i++)
    {
        for (j=0; j<=n; j++)
            for (k=0; k<=n; k++)
                B[i][j][k]=B[i-1][j][k];
        for (j=0; j<n; j++)
            for (k=0; k<n; k++)
                if (B[i-1][j][k])
                {
                    rest=k+A[i];
                    if (rest>=n)
                        rest-=n;
                    B[i][j+1][rest]++;
                    use[i][j+1][rest]=i;
                }
    }
}
void recons(int poz,int left,int rest)
{
    if (left==0)
        return ;
    if (!use[poz][left][rest])
    {
        recons(poz-1,left,rest);
        return ;
    }
    int act=poz,nou;
    nou=rest-A[act];
    if (nou<0)
        nou+=n;
    recons(poz-1,left-1,nou);
    printf("%d ",act);
}
int main()
{
    freopen("congr.in","r",stdin);
    freopen("congr.out","w",stdout);
    read();
    if (n<=300)
    {
        solve1();
        recons(n,n,0);
        return 0;
    }
    return 0;
}