Cod sursa(job #165395)

Utilizator andrei.12Andrei Parvu andrei.12 Data 25 martie 2008 22:15:55
Problema Iv Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#include<string.h>

#define lg 505

int N, n1, n2, i, j, k, h, raspuns, a[lg][lg][lg];
char sir1[lg], sir2[lg];
int main()
{
	freopen("iv.in", "rt", stdin);
	freopen("iv.out", "wt", stdout);

	scanf("%s", sir1+1);
	scanf("%s", sir2+1);

	n1 = strlen(sir1+1), n2 = strlen(sir2+1);
	N = n1 + n2;
//	printf("%d %d\n", n1, n2);

	a[0][0][0] = 1;
	for (i = 0; i <= n1; i ++)
		for (j = 0; j <= n2; j ++)
			//if (i+j <= n1)
				for (k = 0; i+k <= n1; k ++)
					if (i+j-k + j <= n2){
						if (i+j+k + i+j-k == N)
							raspuns += a[i][j][k];
					
						h = i+j-k;

						if (sir1[i+1] == sir1[n1-k])
							a[i+1][j][k+1] += a[i][j][k];
						if (sir1[i+1] == sir2[n2-h])
							a[i+1][j][k] += a[i][j][k];
					
						if (sir2[j+1] == sir1[n1-k])
							a[i][j+1][k+1] += a[i][j][k];
						if (sir2[j+1] == sir2[n2-h])
							a[i][j+1][k] += a[i][j][k];
					}
	for (i = 0; i <= n1; i ++)
		for (j = 0; j <= n2; j ++)
			for (k = 0; k <= n1; k ++);
//				printf("a[%d][%d][%d][%d] = %d\n", i, j, k, i+j-k, a[i][j][k]);

	printf("%d\n", raspuns);

	return 0;
}