Towers of Hanoi Strike Back (URAL 2029)
Problem
The Tower of Hanoi puzzle was invented by French mathematician Édouard Lucas in the second half of the 19th century. Here is its formulation.
There are three rods, denoted by the letters A, B, and C, and n disks of different integer sizes from 1 to n. Initially the disks are stacked in ascending order of size on rod A, the smallest at the top, thus making a conical shape. Each move consists of taking the upper disk from one of the rods and placing it on top of the stack at another rod, with the following condition satisfied: no disk may be placed on top of a smaller disk. The objective of the puzzle is to move the entire stack to rod B in the smallest possible number of moves. The auxiliary rod C can be used in the process.
The state of the rods at each time can be described by a string of n letters A, B, and C: the letter at position i denotes the rod where the disk of size i is at that time. For example, the initial state is given by the string containing letters A only, and the final state is described by the string consisting of letters B. The converse is also true: any such string uniquely describes a valid state of the rods, because the order of disks on a rod is uniquely defined by their size.
Imagine that you are required to pass from the initial state, where all the disks are on rod A, to some prescribed state. What is the smallest number of moves in which this can be done?
Input
The first line contains an integer n (1 ≤ n ≤ 50).
In the second line you are given n uppercase English letters A, B, C, which describe the final state.
Output
If it is impossible to obtain the final state from the initial state, output “-1” (without quotation marks). Otherwise, output the minimum number of moves. It is guaranteed that, if there is an answer, it does not exceed 10 18.
Example
input | output |
---|---|
1 |
0 |
4 |
15 |
7 |
95 |
题解:读懂题意就蛮好做的了,就是汉诺塔的一个变形,让字母移到对应的A、B、C三个柱子上,只需要把所有的都移到相应位置。从最上面开始判断,直到到开始的那个就可以了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
ll a[55];
char s[100];
int main()
{
ll n, i;
a[0] = 0;
a[1] = 1;
for(i = 2; i <= 50; i ++) // 汉诺塔公式
{
a[i] = a[i - 1] * 2 + 1;
}
scanf("%lld",&n);
scanf("%s",s+1);
ll x = 1; // 来表示一开始在的位置
ll ans = 0;
for(i = n; i >= 1; i--) // 如果想要由位置1移到位置3,那么2为跳板,位置x更新为跳板
{
if(x==1&&s[i]=='A') continue;
else if(x==1&&s[i]=='B')
{
ans+=a[i-1]+1;
x=3;
}
else if(x==1&&s[i]=='C')
{
ans+=a[i-1]+1;
x=2;
}
else if(x==2&&s[i]=='A')
{
ans+=a[i-1]+1;
x=3;
}
else if(x==2&&s[i]=='B')continue;
else if(x==2&&s[i]=='C')
{
ans+=a[i-1]+1;
x=1;
}
else if(x==3&&s[i]=='A')
{
ans+=a[i-1]+1;
x=2;
}
else if(x==3&&s[i]=='B')
{
ans+=a[i-1]+1;
x=1;
}
else if(x==3&&s[i]=='C') continue;
}
printf("%lld\n",ans);
return 0;
}
最新文章
- Datazen安装
- Web之路笔记之三 - 使用Floating实现双栏样式
- easyui的getRows和appendRow方法使用结果记录
- 为大家分享一个 Ajax Loading —— spin.js
- 一条诡异的insert语句
- AC日记——统计数字字符个数 openjudge 1.7 01
- Jbuilder 2008安装及破解
- websphere如何删除应用程序服务器(概要管理工具)
- OUYA游戏开发核心技术剖析大学霸内部资料
- 组建自动化工具Ant
- 转】MyEclipse使用总结——MyEclipse中配置WebLogic12c服务器
- 【转】unity3d input输入
- 缩略图类库--ThumbLib使用简介
- Linux Mysql 每天定时备份
- docker ,docker与虚拟机的区别
- Python是如何进行内存管理
- db mysql / mysql cluster 5.7.19 / my.cnf / thread_pool_stall_limit
- gym101657 C
- 【测试工具】http协议调试利器fiddler使用教程
- OTL翻译(10) -- OTL的流缓冲池
热门文章
- php 压缩接口
- 怎样理解 display:none 和 visibility:hidden
- luogu题解 P3763 【[TJOI2017]DNA】
- 用Python获取黄石市近7天天气预报
- ES6入门十一:Generator生成器、async+await、Promisify
- JAVA 1.6锁状态转换
- docker-compose 编排文件小疑点
- 2.6. 案例:使用BeautifuSoup4的爬虫
- PAT Basic 1087 有多少不同的值 (20 分)
- 认识Caffe与Caffe2