首页 > 代码库 > HDU 4260(The End of The World-Hanoi塔从中间状态移动)
HDU 4260(The End of The World-Hanoi塔从中间状态移动)
The End of The World
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 646 Accepted Submission(s): 308
Problem Description
Legend says that there is a group of monks who are solving a large Towers of Hanoi puzzle. The Towers of Hanoi is a well-known puzzle, consisting of three pegs, with a stack of disks, each a different size. At the start, all of the disks are stacked on one of the pegs, and ordered from largest (on the bottom) to smallest (on the top). The object is to move this stack of disks to another peg, subject to two rules: 1) you can only move one disk at a time, and 2) you cannot move a disk onto a peg if that peg already has a smaller disk on it.
The monks believe that when they finish, the world will end. Suppose you know how far they’ve gotten. Assuming that the monks are pursuing the most efficient solution, how much time does the world have left?
The monks believe that when they finish, the world will end. Suppose you know how far they’ve gotten. Assuming that the monks are pursuing the most efficient solution, how much time does the world have left?
Input
There will be several test cases in the input. Each test case will consist of a string of length 1 to 63, on a single line. This string will contain only (capital)As, Bs and Cs. The length of the string indicates the number of disks, and each character indicates the position of one disk. The first character tells the position of the smallest disk, the second character tells the position of the second smallest disk, and so on, until the last character, which tells the position of the largest disk. The character will beA, B or C, indicating which peg the disk is currently on. You may assume that the monks’ overall goal is to move the disks from pegA to peg B, and that the input represents a legitimate position in the optimal solution. The input will end with a line with a single capitalX.
Output
For each test case, print a single number on its own line indicating the number of moves remaining until the given Towers of Hanoi problem is solved. Output no extra spaces, and do not separate answers with blank lines. All possible inputs yield answers which will fit in a signed 64-bit integer.
Sample Input
AAA BBB X
Sample Output
7 0
Source
The University of Chicago Invitational Programming Contest 2012
Recommend
liuyiding | We have carefully selected several similar problems for you:
pid=4257" target="_blank">4257
pid=4261" target="_blank">4261 4262
pid=5390" target="_blank">5390
pid=5389" target="_blank">5389
Hanoi塔给一个中间状态。求到终于状态最小步数。
递归。
每次calc(n,goal) 表示把前n小的盘子全移动到goal的步数。
可递归分解为
{
1.若盘子n本来就在goal上,跳过
2.若盘子n不在goal上,
1)把前n-1个盘子移动到空余的goal2上 calc(n-1,goal2)
2)移动盘子n到goal 1步
3)把n-1个盘子从goal2移到goal上 2^(n-1)-1步
}
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (63+10) typedef long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} char s[MAXN]; int n; ll calc(int n,int goal) { ForD(i,n) { if (s[i]!=goal) { int goal2; if (s[i] + goal == 'A' + 'B' ) goal2='C'; if (s[i] + goal == 'A' + 'C' ) goal2='B'; if (s[i] + goal == 'C' + 'B' ) goal2='A'; return calc(i-1,goal2) + (1LL<<i-1); } } return 0; } int main() { // freopen("hdu4260.in","r",stdin); while(scanf("%s",s+1)==1) { if (s[1]=='X') break; n=strlen(s+1); cout<<calc(n,'B')<<endl; } return 0; }
HDU 4260(The End of The World-Hanoi塔从中间状态移动)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。