Cod sursa(job #18131)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 18 februarie 2007 09:52:53
Problema Culori Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 0.71 kb
#include <stdio.h>
#include <string.h>

#define NMAX 260
#define MMAX 600
#define P 9901

int c[NMAX], Q[MMAX][MMAX];
int i, j, k, p, M, N;

int main()
{
	freopen("culori.in", "r", stdin);

	scanf("%d", &N);
	M = 2 * N - 1;

	for (i = 1; i <= M; i++)
		scanf("%d", &c[i]);
	
	for (i = 1; i <= M; i++)
		Q[i][i] = 1;

	for (k = 2; k <= M; k++)
		for (i = 1; i <= M - k + 1; i++)
		{
			j = i + k - 1;

			if (k % 2 == 0 || c[i] != c[j])
			{
				Q[i][j] = 0;
				continue;
			}

			Q[i][j] = 0;

			for (p = i; p < j; p++)
				if (c[p] == c[i])
					Q[i][j] = (Q[i][j] + Q[i][p] * Q[p + 1][j - 1]) % P;
		}

	freopen("culori.out", "w", stdout);
	printf("%d\n", Q[1][M]);

	return 0;
}