记录编号	73000	评测结果	AAAAATTTTT
题目名称	分裂	最终得分	50
用户昵称	Chenyao2333	是否通过	未通过
代码语言	C++	运行时间	5.930 s
提交时间	2013-10-19 20:14:20	内存使用	95.98 MiB

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

const int MAXN=10000+10;
int n=0;

void open(){
	freopen("mushroom.in","r",stdin);
	freopen("mushroom.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}

void read_date(){
	scanf("%d",&n);
}

struct bign{
	char num[MAXN/2];
	int len;
	
	bign(){
		len=0;
		memset(num,0,sizeof(num));
	}
	
	bign(int i){
		(*this)=i;
	}
	
	bign operator = (int t){
		clear();
		int i=t;
		while(i){
			num[len++]=i%10;
			i/=10;
		} 
	}
	
	bign operator + (bign& b){
		bign a;
		int t=0;
		for(int i=0;i<=len || i<=b.len;i++){
			a.num[i]=num[i]+b.num[i]+t;
			t=a.num[i]/10;
			a.num[i]%=10;
		}
		a.len=len>b.len?len:b.len;
		
		if(a.num[a.len])a.len++;
		return a;
	}
	void clear(){
		len=0;
		memset(num,0,sizeof(num));
	}
	void out(){
		for(int i=len-1;i>=0;i--){
			printf("%d",int(num[i]));
		}
	}
	
}a[MAXN],b[MAXN];

void solve(){
	bign ans;

	a[2].num[0]=1;
	a[2].len=1;
	
	for(int i=2;i<=n;i++){
		b[1]=a[2];
		for(int j=2;j<=i+2;j++){
			b[j]=a[j-1]+a[j+1];	
			a[j-1]=b[j-1];
			b[j-1].clear();
		}
		//for(int k=1;k<=i+1;k++)if(a[k])printf("%d\t",a[k]);
		//printf("\n");
	}
	
	for(int i=1;i<=n+1;i++)ans=ans+a[i];
	ans.out();
}

int main(){
	open();
	
	read_date();
	/*
	bign c(8858888);
	bign d(9999);
	d=d+c;
	d.out();*/
solve();
//	printf("%lld",ans);
	
close();
	return 0;
}