10795 - A Different Task
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=456&page=show_problem&problem=1736
The (Three peg) Tower of Hanoi problem is a popular one in computer science. Briefly the problem is to transfer all the disks from peg-A to peg-C using peg-B as intermediate one in such a way that at no
stage a larger disk is above a smaller disk. Normally, we want the minimum number of moves required for this task. The problem is used as an ideal example for learning recursion. It is so well studied that one can find the sequence of moves for smaller number
of disks such as 3 or 4. A trivial computer program can find the case of large number of disks also.
Here we have made your task little bit difficult by making the problem more flexible. Here the disks can be in any peg initially.
If more than one disk is in a certain peg, then they will be in a valid arrangement (larger disk will not be on smaller ones). We will give you two such arrangements of disks. You will have to find out the minimum number of moves, which will transform the
first arrangement into the second one. Of course you always have to maintain the constraint that smaller disks must be upon the larger ones.
The input file contains at most 100 test cases. Each test case starts with a positive integer
N ( 1N60),
which means the number of disks. You will be given the arrangements in next two lines. Each arrangement will be represented by
N integers, which are 1,
2 or 3. If the i-th (
1iN)
integer is 1, you should consider that i-th disk is on Peg-A. Input is terminated by
N = 0. This case should not be processed.
Output of each test case should consist of a line starting with `Case
#: ' where # is the test case number. It should be followed by the minimum number of moves as specified in the problem statement.
3
1 1 1
2 2 2
3
1 2 3
3 2 1
4
1 1 1 1
1 1 1 1
0
Case 1: 7
Case 2: 3
Case 3: 0
思路:首先找最大不在目标柱子上的盘子K,因为如果最大的盘子在目标柱子上它不需要移动,也不碍事。
因此问题就成了把K移动到目标柱子,把1到(k-1)移动到中转柱子,所以假设K从A移动到B,A只有K,B是空的,C上面是K-1到1,把这个局面称为参考局面。因为移动是对称的,所以从参考局面移到目标局面与目标局面移到参考局面是一样的步数。
所以问题变成答案=从初始局面移到参考局面步数+目标局面移到参考局面步数+1;
需要写一个函数f(P,i,final),表示已知个盘子的初始柱面编号数组为P,把1到i移动到final的步数,本题答案是f(start,k-1,start[k]^finish[k])+f(finish,k-1,start[k]^finish[k])+1;(技巧:1^2=3,1^3=2,2^3=1)
计算f(P,i,final),若p[i]=final,则f(P,i,final)=f(P,i-1,final);否则需要把前i-1个盘子挪到中转盘去,将盘子i移到柱子final去,做后把前i-1个盘子从中转盘移到柱子final.。最后一步是把i-1个盘子从一个柱子移到另一个柱子,根据旧汉诺塔问题,这个步骤需要2^(i-1)-1步,加上移动盘子i那一步,一共需要2^(i-1)步。
f(P,i,final)=f(P,i-1,p[i]^final)+2^(i-1);
完整代码:
/*0.019s*/
#include<cstdio>
const int maxn = 65;
int n, start[maxn], finish[maxn];
long long f(int* P, int i, int final)
{
if (i == 0) return 0;
if (P[i] == final) ///表示这个盘子已经到位了
return f(P, i - 1, final);
return f(P, i - 1, P[i] ^ final) + (1LL << (i - 1));
}
int main()
{
int kase = 0;
while (scanf("%d", &n), n)
{
for (int i = 1; i <= n; i++) scanf("%d", &start[i]);
for (int i = 1; i <= n; i++) scanf("%d", &finish[i]);
int k = n;
while (k >= 1 && start[k] == finish[k])
k--;///找初始局面和目标局面所在柱子不同的最大盘子
long long ans = 0;
if (k >= 1)
ans = f(start, k - 1, start[k] ^ finish[k]) + f(finish, k - 1, start[k] ^ finish[k]) + 1;
printf("Case %d: %lld\n", ++kase, ans);
}
return 0;
}
分享到:
相关推荐
主要是uvaoj习题相关题目 练习题目
UVA 题目,不是很难,试试吧
UVA【UVA1267】Network拓展题:咖啡店数据 内含标程以及数据生成器
这个是书里采用的习题和例题的UVa原题pdf(英文)。 分享这个文件的原因是国内上UVa太慢了,有时候UVa还会挂。 而且书里把输入输出样例省去了,这里整理出原题做个参考。 所以我把书里3-12章的每道例题和习题的UVa原...
算法竞赛入门经典(第二版)的习题都是UVa上的, 但是UVa太慢了太慢了太慢了太慢了太慢了, 于是我把各章习题的pdf一次性打包下载到本地, 和大家分享:)
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
ACM UVA 动态规划 文档里有UVAOJ上面大量的DP练习题,可以说认真做完之后,你的DP不是问题。
收集了刘汝佳的算法竞赛入门经典这本书的所有在uva上的课后习题,按照章节分类,全部为pdf格式
自己整理的UVa所有题目的PDF题面,可根据目录中的Volume快速跳转(与UVa官网一致)。 题目共4965题,PDF共8380页,可能会出现打开较慢的问题。 关于某个题目所在位置的判断方法: 题号除了后两位的其他数字构成...
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
其实官网上每道题都有一个PDF提供下载,这里是方便手懒的同学··· 其实刚刚就从下载频道下了一个名为 “算法入门经典UVa配套题目pdf”的文件,也是题目PDF,不过缺少Volume 0 以及Volume 3多了一个压缩包,所以...
UVA109的题解,经测试完全正确,还附有题解。
uva272
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
uva最全ac代码
PDF试题
c++的算法题四分树的实现-uva10771
uva10755 ac 代码,可以随意更改下载