Cod sursa(job #137703)

Utilizator diac_paulPaul Diac diac_paul Data 17 februarie 2008 12:57:18
Problema Arbori Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasele 11-12 Marime 1.8 kb
#include <stdio.h>
//#define llong long long
#define NMax 100

int n, m, k;
int i, j, l, f, t, u;
long long p[NMax], a[NMax][NMax][NMax];

int main()
{
	FILE *fin = fopen("arbori.in", "rt");
	FILE *fout = fopen("arbori.out", "wt");

	fscanf(fin, "%d %d %d", &n, &m, &k);
	if (k == 0)
		k = m;

	p[1] = 1;

	for (i = 2; i < n; i++) // i noduri in total, raman i - 1
	{
		for (j = k - 1; j < i; j += m) // j fii directi
		{
			for (f = 0; f < j; f++)
			{
				for (t = 0; t < i; t++)
				{
					for (u = 0; u < t; u++)
					{
						a[f][t][u] = 0;
					}
				}
			}

			for (u = 0; u < i; u++) // pun pe primul fiu
				a[0][u][u] = p[u];
			
			for (f = 1; f < j; f++) // f ultimul fiu
			{
				for (t = 0; t < i; t++) // t noduri in total
				{
					for (u = 1; u < t; u++) // u noduri pe ultimul fiu, t - u in rest
					{
						for (l = 0; l <= t - u && l <= u; l++) // k noduri pe fiul f - 1
						{
							a[f][t][u] += a[f-1][t - u][l] * p[u];
						}
					}
				}
			}

			for (l = 0; l < i; l++)
				p[i] += a[j-1][i-1][l];
		}
	}


	for (j = k; j < n; j += m) // j fii directi
	{
		for (f = 0; f < j; f++)
		{
			for (t = 0; t < n; t++)
			{
				for (u = 0; u <= t; u++)
				{
					a[f][t][u] = 0;
				}
			}
		}

		for (u = 0; u < n; u++) // pun pe primul fiu
			a[0][u][u] = p[u];
			
		for (f = 1; f < j; f++) // f ultimul fiu
		{
			for (t = 0; t < n; t++) // t noduri in total
			{
				for (u = 1; u < t; u++) // u noduri pe ultimul fiu, t - u in rest
				{
					for (l = 0; l <= t - u && l <= u; l++) // k noduri pe fiul f - 1
					{
						a[f][t][u] += a[f-1][t - u][l] * p[u];
					}
				}
			}
		}

		for (l = 0; l < n; l++)
			p[i] += a[j-1][i-1][l];
	}

	fprintf(fout, "%lld\n", p[n]);

	fclose(fin);
	fclose(fout);

	return 0;
}