链接：https://ac.nowcoder.com/acm/contest/3004/I

汉诺塔是一个经典问题，相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置n个金盘。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

 

汉诺塔以及其衍生问题往往使用递归来求解，也是学习和理解递归很好的老师。

 

其伪代码如下

Function Hanoi(n,a,b,c)
    if n==1 then
        print(a+'->'+c)
    else
        Hanoi(n-1,a,c,b)
        print(a+'->'+c)
        Hanoi(n-1,b,a,c)
    end if
end Function 

 

牛牛很快就理解了代码的意思并且写出了求解汉诺塔的程序，他现在想研究汉诺塔的规律。

请你统计以下信息：A->B,A->C,B->A,B->C,C->A,C->B的次数，以及所有移动的总步数。

 

 

输入描述:

 

仅一行，输入一个正整数n(1 \leq n \leq 60)(1≤n≤60)表示汉诺塔的层数。

输出描述:

 

首先输出6行

A->B:XX
A->C:XX
B->A:XX
B->C:XX
C->A:XX
C->B:XX

分别表示每种移动情况出现的次数

最后输出一行
SUM:XX

表示所有移动情况的总和。

示例1

输入

复制

3

输出

复制

A->B:1
A->C:3
B->A:1
B->C:1
C->A:0
C->B:1
SUM:7

说明

 

伪代码所示算法的移动序列如下：

A->C

A->B
C->B
A->C
B->A
B->C

A->C

统计：

A->B出现1次

A->C出现3次

B->C出现1次

B->A出现1次

C->B出现1次

总计7次

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,m,t,g,l,s1=0,s2=0,s3=0,s4=0,s5=0,s6=0,w,o,r,ans,s=0,max1=0,min1=0;
long long ppow(long long a, long long b)
{
	long long ans = 1;
	while(b > 0){
		if(b & 1){
			ans = ans * a ;
		}
		a = a * a ;
		b >>= 1; 
	} 
	return ans;
}

int main()
{
	cin>>n;
	s=ppow(2,n)-1;
	g=1;
	if(n==1)
	s2=1;
	for(int i=2,k=1;i<=n+2;i++)
	{
		if(i%2==1)
		{
			g=g*4-k;
			k+=2;
		}
		if(i==n)
		s2=g;
		if(i==n+1)
		{
			s1=(g-1)/2;
			s4=s1;
		}
	}
	if(n<=2)
	{
		s3=0;
		s5=0;
		s6=0;
	}
	else if(n==3)
	{
		s3=1;
		s6=1;
	}
	else if(n==4)
	{
		s3=1;
		s6=1;
		s5=2;
	}
	else
	{
		g=1;
		for(int i=5,k=2;i<=n+2;i++)
		{
			if(i%2==1)
			{
				g=g*4+k;
				k++;
			}
			if(i==n)
			{
				s3=g;
				s6=g;	
			}
			if(i==n-1)
			{
				s5=g*2;
			}
		}
		if(n==5)
		s5=2;
	}
	cout<<"A->B:"<<s1<<endl;
	cout<<"A->C:"<<s2<<endl;
	cout<<"B->A:"<<s3<<endl;
	cout<<"B->C:"<<s4<<endl;
	cout<<"C->A:"<<s5<<endl;
	cout<<"C->B:"<<s6<<endl;
	cout<<"SUM:"<<s<<endl;
}