poj 3572 Hanoi Tower

Hanoi Towers

Time Limit : 10000/5000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 0 Accepted Submission(s) : 0

Special Judge

Problem Description

The “Hanoi Towers” puzzle consists of three pegs (that we will name A, B, and C) with n disks of different diameters stacked onto the pegs. Initially all disks are stacked onto peg A with the smallest disk at the top and the largest one at the bottom, so that they form a conical shape on peg A.

Input

The input file contains two lines. The first line consists of a single integer number n (1 ≤ n ≤ 30) the number of disks in the puzzle. The second line contains descriptions of six moves separated by spaces the strategy that is used to solve the puzzle.

Output

Write to the output file the number of moves it takes to solve the puzzle. This number will not exceed 10¹⁸.

Sample Input

#1	3 AB BC CA BA CB AC
#2	2 AB BA CA BC CB AC

Sample Output

#1	7
#2	5

貌似是一道纯规律的题，我不会做。。。照着网上的规律敲了一遍，感觉网上的大神真厉害。

题意：对于一个汉诺塔，每次按照给定的顺序，找第一个可以移动的方式去移动。要求不能大的下面放小的，且不能连续两次移动同一个盘子。

附上代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 typedef long long ll;
 5 ll a[40],b[40],c[40];
 6 int num[10];
 7 char s[10];
 8 int main()
 9 {
10     int n,i,j,k;
11     a[1]=b[1]=c[1]=1;
12     for(i=2; i<=30; i++)
13     {
14         a[i]=a[i-1]*2+1;
15         c[i]=c[i-1]*3+2;
16         b[i]=b[i-1]+c[i-1]+1;
17     }
18     scanf("%d",&n);
19     for(i=1; i<=6; i++)
20     {
21         scanf("%s",s);
22         k=(s[0]-'A')*4+s[1]-'A';
23         num[k]=i;
24     }
25     if(num[1]<num[2])
26     {
27         if(num[4]<num[6])
28             printf("%I64d
",c[n]);
29         else if(num[9]<num[8])
30             printf("%I64d
",b[n]);
31         else
32             printf("%I64d
",a[n]);
33     }
34     else
35     {
36         if(num[8]<num[9])
37             printf("%I64d
",c[n]);
38         else if(num[6]<num[4])
39             printf("%I64d
",b[n]);
40         else
41             printf("%I64d
",a[n]);
42     }
43 }