Cod sursa(job #165442)

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

#define nmax 22

char A[nmax], B[nmax];

int N, M, P, ans, NRP[nmax][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 + (M+N)%2; i <= P; ++i)
		for (x = 1; x <= i; ++x)
			for (y = 1; y <= i; ++y)
			{
				if (A[x] == A[N-y+1])
					NRP[i][x][y] += NRP[i-1][x-1][y-1];
				if (A[x] == B[N-i+y+1])
					NRP[i][x][y] += NRP[i-1][x-1][y];
				if (B[i-x] == A[N-y+1])
					NRP[i][x][y] += NRP[i-1][x][y-1];
				if (B[i-x] == B[N-i+y+1])
					NRP[i][x][y] += NRP[i-1][x][y];
			}

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

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

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

int main()
{
	read();

	solve();

	write();

	return 0;
}