Cod sursa(job #165469)

Utilizator vlad.maneaVlad Manea vlad.manea Data 25 martie 2008 23:39:49
Problema Iv Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <string.h>

#define nmax 555

char A[nmax], B[nmax];

int N, M, P, i2, i21, ans, NRP[2][nmax][nmax];

void read()
{
	freopen("iv.in", "r", stdin);

	scanf("%s", &A);

	scanf("\n");

	scanf("%s", &B);
}

void solve()
{
	int i, x, y;

	N = strlen(A);

	M = strlen(B);

	for (i = N; i >= 1; i--)
		A[i] = A[i-1];

	for (i = M; i >= 1; i--)
		B[i] = B[i-1];

	A[0] = B[0] = ' ';

	// pentru cazul elementar
	if (A[1] == A[N])
		NRP[1][1][1] = 1;

	if (A[1] == B[M])
		NRP[1][1][0] = 1;

	if (B[1] == A[N])
		NRP[1][0][1] = 1;

	if (B[1] == B[M])
		NRP[1][0][0] = 1;

	for (i = 2, P = (M+N)/2; i <= P; ++i)
		for (i2 = i%2, i21 = (i-1)%2, x = 0; x <= i; ++x)
			for (y = 0; y <= i; ++y)
			{
				NRP[i2][x][y] = 0;
				if (x + y <= N && i-x + i-y <= M)
				{
					if (x > 0 && N-y+1 <= N && A[x] == A[N-y+1])
						NRP[i2][x][y] += NRP[i21][x-1][y-1];
					if (x > 0 && M-i+y+1 <= M && A[x] == B[M-i+y+1])
						NRP[i2][x][y] += NRP[i21][x-1][y];
					if (i-x > 0 && N-y+1 <= N && B[i-x] == A[N-y+1])
						NRP[i2][x][y] += NRP[i21][x][y-1];
					if (i-x > 0 && M-i+y+1 <= M && B[i-x] == B[M-i+y+1])
						NRP[i2][x][y] += NRP[i21][x][y];
				}
			}

	for (x = 0; x <= P; ++x)
		for (y = 0; y <= P; ++y)
			ans += NRP[P%2][x][y];
}

void write()
{
	freopen("iv.out", "w", stdout);

	printf("%d\n", ans);
}

int main()
{
	read();

	solve();

	write();

	return 0;
}