比赛 NOIP2007普及组(复现) 评测结果 AAAAAAAAAA
题目名称 Hanoi双塔问题 最终得分 100
用户昵称 斯内普和骑士 运行时间 0.006 s
代码语言 C++ 内存使用 13.66 MiB
提交时间 2020-02-09 15:54:43
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
struct BigNum
{
	int d[1000];
	int len;
	BigNum()
	{
		memset(d,0,sizeof(d));
		len=0;
	}
};
BigNum init(string s)
{
	BigNum x;
	x.len=s.size();
	for(int i=0;i<s.size();i++)
	x.d[i]=s[s.size()-i-1]-'0';
	return x;
}
void CTJ(BigNum a)
{
	for(int i=a.len-1;i>=0;i--)
	cout<<a.d[i];
}
BigNum sub(BigNum a,BigNum b)
{
	BigNum c;
	c.len=max(a.len,b.len);
	for(int i=0;i<c.len;i++)
	{
		if(a.d[i]<b.d[i])
		{
			a.d[i+1]--;
			a.d[i]+=10;
		}
		c.d[i]=a.d[i]-b.d[i];
	}
	while(c.len>1&&c.d[c.len-1]==0)
	c.len--;
	return c;
}
BigNum multia(BigNum a,int b)
{
	BigNum c;
	int carry=0;
	for(int i=0;i<a.len;i++)
	{
		int t=a.d[i]*b+carry;
		c.d[c.len++]=t%10;
		carry=t/10;
	}
	while(carry)
	{
		c.d[c.len++]=carry%10;
		carry/=10;
	}
	return c;
}
BigNum mypow(int b)
{
	BigNum c;
	c.d[0]=1;
	c.len=1;
	for(int i=0;i<b;i++)
		c=multia(c,2);
	c=sub(c,init("1"));
	c=multia(c,2);
	return c;
}
int main()
{
	freopen("hanoi.in","r",stdin);
	freopen("hanoi.out","w",stdout);
	int R;
	cin>>R;
	CTJ(mypow(R));
	return 0;
}