比赛 20110728 评测结果 WWAAAAWWAW
题目名称 汉诺塔 最终得分 50
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-28 11:17:28
显示代码纯文本
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN=35,MAXM=205,MAXL=100;
const int oo=~0u>>2;

struct High;
ostream & operator << (ostream &out,const High &a);

struct High
{
	int len,a[MAXL];
	bool operator >= (const High &b) const
	{
		if (len!=b.len)
			return len>b.len;
		for(int i=len-1;i>=0;i--)
			if (a[i]!=b.a[i])
				return a[i]>b.a[i];
		return true;
	}
	bool operator != (const int &x) const
	{
		assert(x==oo);
		return len!=MAXL;
	}
	High operator + (const High &b) const
	{
		High c;
		c.len=max(len,b.len);
		for(int i=0;i<c.len;i++)
		{
			c.a[i]+=a[i]+b.a[i];
			if (c.a[i]>=10)
			{
				c.a[i]-=10;
				c.a[i+1]++;
			}
		}
		if (c.a[c.len]!=0)
			c.len++;
	//	cerr<<*this<<" + "<<b<<" = "<<c<<endl;
		return c;
	}
	High operator * (const int &x) const
	{
		assert(x==2);
		High c=*this;
		for(int i=0;i<c.len;i++)
			c.a[i]*=x;
		for(int i=0;i<c.len;i++)
			if (c.a[i]>=10)
			{
				c.a[i]-=10;
				c.a[i+1]++;
			}
		if (c.a[c.len]!=0)
			c.len++;
	//	cerr<<*this<<" * "<<x<<" = "<<c<<endl;
		return c;
	}
	High(int x)
	{
		memset(a,0,sizeof(a));
		if (x!=oo)
		{
			assert(x==0 || x==1);
			len=1,a[0]=x;
		}
		else
		{
			assert(x==oo);
			len=MAXL;
		}
	}
	High()
	{
		len=1;
		memset(a,0,sizeof(a));
	}
};

ostream & operator << (ostream &out,const High &a)
{
	for(int i=a.len-1;i>=0;i--)
		out<<a.a[i];
	return out;
}

int N,M;
High d[MAXM],g[MAXN][MAXM];
int maxdep;

int main()
{
	freopen("ionah.in","r",stdin);
	freopen("ionah.out","w",stdout);
	cin>>N>>M;
	maxdep=N-2;
	for(int i=0;i<=maxdep;i++)
		for(int j=0;j<=M-1;j++)
			g[i][j]=oo;
	g[0][0]=0;
	d[1]=1;
	for(int i=1;i<=M;i++)
	{
		if (i!=1)
			d[i]=g[maxdep][i-1]*2+1;
		for(int k=0;k<maxdep;k++)
			for(int j=0;j+i<=M-1;j++)
				if (g[k][j]!=oo)
				{
					High t=g[k][j]+d[i];
					if (!(t>=g[k+1][j+i]))
						g[k+1][j+i]=t;
					if (!(g[k][j]>=g[k+1][j]))
						g[k+1][j]=g[k][j];
				}
	}
	cout<<d[M]<<endl;
	return 0;
}