比赛 20110728 评测结果 AAAAAAAAAA
题目名称 汉诺塔 最终得分 100
用户昵称 .Xmz 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-28 09:04:15
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

int n,m;
long long f[31][201];

struct bignumber
{
	int x[201];
	void print()
	{
		bool yy=false;
		for (int i=200;i>0;i--)
		if (x[i]!=0 || yy)
		{
			yy=true;
			printf("%d",x[i] - (i==1 ? 1 : 0) );
		}
		printf("\n");
	}
}X;

bignumber operator + (bignumber &a,bignumber &b)
{
	bignumber c;
	memset(c.x,0,sizeof(c.x));
	int delta=0;
	for (int i=1;i<=200;i++)
	{
		c.x[i]=a.x[i]+b.x[i]+delta;
		delta=c.x[i]/10;
		c.x[i]%=10;
	}
	return c;
}

int main()
{
	freopen("ionah.in","r",stdin);
	freopen("ionah.out","w",stdout);
	scanf("%d%d",&n,&m);
	if (n==3)
	{
		X.x[1]=1;
		for (int i=1;i<=m;i++) X=X+X;
		X.print();
	}
	if (n!=3)
	{
		for (int i=3;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			if (i==3) f[i][j]=((long long)1<<min(60,j))-1;
			else if (j==1) f[i][j]=1;
			else
			{
				for (int k=j-1;k>=1;k--)
				{
					if ( k==j-1 || f[i][j]>2*f[i][k]+f[i-1][j-k] ) 
					f[i][j]=2*f[i][k]+f[i-1][j-k];
				}
			}
		}
		printf("%lld\n",f[n][m]);
	}
	return 0;
}