Cod sursa(job #212235)
Utilizator | Data | 4 octombrie 2008 20:05:23 | |
---|---|---|---|
Problema | Culori | Scor | 48 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.01 kb |
#include<stdio.h>
#define NMAX 512
int V[NMAX],D[NMAX][NMAX];
int main()
{
freopen("culori.in","r",stdin);
freopen("culori.out","w",stdout);
int N;
scanf("%d",&N);
N<<=1;--N;
int i;
for(i=0; i<N; ++i)
{
scanf("%d",&V[i]);
D[i][i]=1;
}
int gap,j,k;
for(gap=1; gap<N; ++gap)
{
for(i=0; i+gap<N; ++i)
{
j=i+gap;
if( V[i]==V[j] && (i+j)%2==0 )
{
for(k=i+1; k<=j; ++k)
{
if( V[i+1]==V[k] && V[k+1]==V[j] ) //more or less useless
D[i][j]+=D[i+1][k]*D[k+1][j];
}
}
D[i][j]%=9901;
}
}
printf("%d\n",D[0][N-1]);
return 0;
}