uva----(10794) A Different Task

A Different Task

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.

Input 

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 12 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 

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.

Sample Input 

3
1 1 1
2 2 2
3
1 2 3
3 2 1
4
1 1 1 1
1 1 1 1
0

Sample Output 

Case 1: 7
Case 2: 3
Case 3: 0

 代码:

 1 #include<cstdio>
 2 const int maxn =70;
 3 int n,start[maxn],finish[maxn];
 4 long long Func(int *p,int i,int final)
 5 {
 6     if(i==0) return 0;
 7     if(p[i]==final) return Func(p,i-1,final);
 8     return Func(p,i-1,6-p[i]-final)+(1LL<<(i-1));
 9 }
10 int main()
11 {
12     int kase=0;
13     while(scanf("%d",&n)==1&&n)
14     {
15       for(int i=1;i<=n;i++)
16             scanf("%d",&start[i]);
17       for(int i=1;i<=n;i++)
18           scanf("%d",&finish[i]);
19       int k=n;
20       while(k>=1 && start[k]==finish[k])k--;
21       
22       long long ans=0;
23       if(k>=1)
24       {
25           int other=6-start[k]-finish[k];
26           ans =Func(start,k-1,other)+Func(finish,k-1,other)+1;
27       }
28       printf("Case %d: %lld\n",++kase,ans);
29     }
30 }

Problem setter: Md. Kamruzzaman

Special Thanks: Derek Kisman (Alternate Solution), Shahriar Manzoor (Picture Drawing)


Miguel Revilla 2004-12-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊flink的FsCheckpointStreamFactory

flink-runtime_2.11-1.7.0-sources.jar!/org/apache/flink/runtime/state/CheckpointS...

12920
来自专栏河湾欢儿的专栏

判断语句

算术运算符:+ - * / % ++ -- 一元运算符:++ -- ! 逻辑运算符:&||! 比较运算符 == === != > < >= <= ...

7710
来自专栏javascript趣味编程

5.2.3 二维导热算例-整体架构

14300
来自专栏码匠的流水账

聊聊rocketmq的BrokerHousekeepingService

本文主要研究一下rocketmq的BrokerHousekeepingService

11910
来自专栏海天一树

小朋友学Java(11):枚举

在C/C++/Java中,数据类型可以分为两大类。 一类是基本类型,比如int, long, float, double, char, String等 另一类是...

27560
来自专栏数据结构与算法

Tour UVA - 1347

John Doe, a skilled pilot, enjoys traveling. While on vacation, he rents a small...

35950
来自专栏码匠的流水账

聊聊flink的OperatorStateBackend

flink-runtime_2.11-1.7.0-sources.jar!/org/apache/flink/runtime/state/OperatorSta...

30420
来自专栏码匠的流水账

聊聊storm WindowTridentProcessor的FreshCollector

本文主要研究一下storm WindowTridentProcessor的FreshCollector

9530
来自专栏HansBug's Lab

3097: Hash Killer I

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

24340
来自专栏数据之美

java 中 16 进制 HEX 转换成字节码形式的 UTF-8

恩,又碰到个蛋疼的编码转换问题了:要把形如 \xE9\xBB 的字符串转成中文。。。 在python中我们直接 print "\xE9\xBB\x84" ...

28150

扫码关注云+社区

领取腾讯云代金券