当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1920:Towers of Hanoi

题目描述
Surely you have already come across the Towers of Hanoi problem: Wooden disks of different sizes are stacked on three pegs, and initially, all disks are stacked on the same peg sorted by size, with the largest disk at the bottom. The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never putting a larger disk onto a smaller one.
According to an old myth, the monks at an ancient Tibetian monastery have been trying to solve an especially large instance of this problem with 47 disks for thousands of years. Since this requires at least 247 - 1 moves and the monks started out without a strategy, they messed it all up while still following the rules. Now they would like to have the disks stacked up neatly on any arbitrary peg using the minimum number of moves. But they all took a vow which forbids them to move the disks contrary to the rules. They want to know on which peg they should best stack the disks, and the minimum number of moves needed.
Write a program that solves this problem for the monks. Your program should also be able to handle any number N (0 < N <= 100 000) of disks. The numbers involved in the computation can become quite large. Because of that, the monks are only interested in the number of moves modulo 1 000 000.
Example
The following example can be solved in four moves.

输入解释
The first line of the input file hanoi.in consists of the number N (N <= 100000) of disks. The second line consists of three integers s1, s2, s3 with 0 <= s1, s2, s3 <= N and s1+s2+s3 = N, the number of disks on each of the three pegs. Lines three to five each contain the sizes of the disks for one peg. More precisely:
The (i + 2)-th line of the input file consists of integer numbers mi,1 . . .mi,si with 1 <= mi,j <= N, the sizes of the disks on peg i. The disks are given from bottom to top, thus mi,1 > mi,2 > . . . > mi,si .
Note that an empty stack is given by an empty line. The set of N disks have different sizes. All numbers are separated by a single space.
输出解释
The first line of the output file hanoi.out consists of the number d in {1, 2, 3} of the peg onto which the disks can be stacked using the minimum number of moves. The second line consists of the number M of required moves modulo 1 000 000.
输入样例
7
2 1 4
2 1
3
7 6 5 4
输出样例
3
4
来自北京大学POJ的附加信息
Case time limit(单组数据时间限制) 1000MS

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 CEOI 2003

源链接: POJ-1920

最后修改于 2020-10-29T06:17:51+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
3000 16000