比赛 20111108 评测结果 AAAWWTTTTT
题目名称 分裂 最终得分 30
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-11-08 10:02:33
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=11111;
const int jin=10000000;

struct shu
{
	int num[202];
	shu()
	{
		for (int i=0;i<=200;i++)
			num[i]=0;
	}
}f[2][MAXN],ans;

int n,i,j,k,h;

void add(shu &A,shu B)
{
	for (int i=1;i<=200;i++)
	{
		A.num[i]=B.num[i]+A.num[i]+A.num[i-1]/jin;
		A.num[i-1]=A.num[i-1]%jin;
	}
}

int main()
{
	freopen("mushroom.in","r",stdin);
	freopen("mushroom.out","w",stdout);
	scanf("%d",&n);
	--n;
	f[0][2].num[1]=1;
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=i+2;j++)
		{
			f[i%2][j]=f[(i+1)%2][j+1];
			if (j>1) add(f[i%2][j],f[(i+1)%2][j-1]);
		}
	}
	for (i=1;i<MAXN;i++)
		add(ans,f[n%2][i]);
	h=200;
	while (ans.num[h]==0 && h>1) --h;
	printf("%d",ans.num[h]);
	--h;
	while (h--)
	{
		if (ans.num[h]<1000000) printf("0");
		if (ans.num[h]<100000) printf("0");
		if (ans.num[h]<10000) printf("0");
		if (ans.num[h]<1000) printf("0");
		if (ans.num[h]<100) printf("0");
		if (ans.num[h]<10) printf("0");
		printf("%d",ans.num[h]);
	}
	printf("\n");
	return 0;
}