10303 - How Many Trees?

[little joey]

Your input handling is incorrect. The program tries to read beyond the end of input (and improperly reports this error as Wrong Answer).
The proper way is:
[pascal]while not eof do begin
readln(n);
//calculate and print the answer
end;[/pascal]
If you change it that way, you'll get accepted, because your calculation gives the right answer.

[medv]

Thank you very much!
I got accepted!
Do you have some difficults in solving? - I will help you (if I can)

[mohsincsedu]

I got TLE
Plz tell me the Algorithm
Here is my code:

Code: Select all

#include<stdio.h>
#include<string.h>

#define M 1001
#define MAX 1001

void Add(char *a, char *b, char *c)
{
	int carry = 0,len_a,len_b,k,i,j;
	len_a = strlen(a);
	len_b = strlen(b);
	strcpy(c,"0");
	if(len_b>len_a)
		Add(b,a,c);
	k = len_a + 1;
	c[k--] = '\0';
	for(i = len_a-1, j = len_b-1; j>=0; i--, j--)
	{
		carry = a[i] + b[j] + carry - 2*48;
		c[k--] = carry%10 + 48;
		carry/=10;
	}
	for(;i>=0;i--)
	{
		carry = a[i] + carry - 48;
		c[k--] = carry%10 + 48;
		carry /= 10;
	}
	if(carry)
		c[k] = carry + 48;
	else
	{
		char string[MAX];
		strcpy(string,&c[1]);
		strcpy(c,string);
	}

}

void Sub(char *a, char *b, char *c)
{
	int len_a,len_b,k,i,j,temp,op = 0;

	len_a = strlen(a);
	len_b = strlen(b);
	k = len_a;
	c[k--] = '\0';
	for(i = len_a-1, j = len_b-1; j>=0; i--, j--)
	{
		temp = a[i] - b[j] - op;
		if(temp<0)
		{
			temp+=10;
			op = 1;
		}
		else
			op = 0;
		c[k--] = temp + 48;
	}
	while(op)
	{
		temp = a[i--] - op -48;
		if(temp<0)
		{
			temp+=10;
			op = 1;
		}
		else
			op = 0;
		c[k--] = temp + 48;
	}
	for(;i>=0;i--)
		c[k--] = a[i];
	for(i = 0; !(c[i]-48);i++);
	if(i == len_a)
		strcpy(c,"0");
	else
	{
		char string[MAX];
		strcpy(string,&c[i]);
		strcpy(c,string);
	}
}

void Mul(char *a, char *b, char *c)
{
	short int num1[MAX],num2[MAX],res[MAX] = {0},op = 0;
	int i,j,k,len_a,len_b;
	len_a = strlen(a);
	len_b = strlen(b);
	if(len_a>len_b)
		k = len_a;
	else
		k= len_b;
	k++;
	for(i = 0, j = len_a - 1; j>=0; j--,i++)
		num1[i] = a[j] - 48;
	for(i = 0, j = len_b - 1; j>=0; i++,j--)
		num2[i] = b[j] - 48;
	res[0] = 0;
	for(i = 0; i<len_b; i++)
	{
		for(j = 0, k = i; j<len_a||op;j++,k++)
		{
			if(j<len_a)
				res[k] += num1[j] * num2[i] + op;
			else
				res[k] += op;
			op = res[k]/10;
			res[k]%=10;

		}
	}
	for(i = k - 1, j = 0; i >= 0; i--, j++)
		c[j] = res[i] + 48;
	c[j] = '\0';
}

int compare(char *a, char *b)
{
	int len_a, len_b,i;
	len_a = strlen(a);
	len_b = strlen(b);
	if(len_a>len_b)
		return 1;
	if(len_b>len_a)
		return -1;
	for(i = 0; i<len_a;i++)
	{
		if(a[i]>b[i])
			return 1;
		if(b[i]>a[i])
			return -1;
	}
	return 0;
}

void Div(char *a, char *b, char *c, char *d)
{
	char x[MAX], y[MAX], temp[MAX];

	strcpy(c,"0");
	strcpy(y,"1");
	strcpy(x,a);
	while(compare(x,b)!=-1)
	{
		Sub(x,b,d);
		Add(c,y,temp);
		strcpy(x,d);
		strcpy(c,temp);
	}
}


void main()
{
	char a[MAX],b[MAX],c[MAX],d[MAX];
	char C[M][MAX];
	int i,n;
	strcpy(C[0],"1");
	for(i = 1;i<M;i++)
	{
		n = (4*i-2);
		sprintf(a,"%d",n);
		Mul(C[i-1],a,b);
		n = i + 1;
		sprintf(a,"%d",n);
		Div(b,a,C[i],d);
	}
	while(scanf("%d",&n)!=EOF)
	{
		printf("%s\n",C[n]);
	}

}

[Solaris]

You may find the following link useful

http://mathworld.wolfram.com/CatalanNumber.html

[Feng]

It looks like a straightforward question. I used the formula of Catalan numbers and the C "bignum" routines. But I kept getting TLE. Is there any trick to improve the running time? BTW, which is more costly, bignum multiplication or bignum division?