#O1005. 汉诺塔的第k步
汉诺塔的第k步
汉诺塔的第 步
题目描述
有 、、 三根柱子, 柱上从下到上依次摞着编号为 的 个盘子(编号越小盘子越小)。要求把所有盘子按原顺序移动到 柱,移动过程中:
- 每次只能移动一个盘子,且只能从某根柱子的顶端取走、放到另一根柱子的顶端;
- 任何时候都不能把大盘子放在小盘子上面。
按最少步数完成移动的方案是唯一的,其移动次数为 。现在给定 和 ,请求出:
- 最少移动次数 ;
- 第 次移动的是编号为几的盘子(若 ,输出 )。
输入格式
一行两个整数 。
输出格式
一行两个整数,分别为最少移动次数 与第 次移动的盘子编号(或 ),之间用一个空格隔开。
样例 #1
样例输入 #1
3 4
样例输出 #1
7 3
样例说明
时的移动顺序为:,共 步。第 步移动的是 号盘子。
数据规模与约定
| 数据范围 | ||
|---|---|---|
| 全部测试点 |
- ,超出 32 位整数范围,请使用 64 位无符号整数。
- 不需要模拟移动过程,注意观察第 步与 的二进制表示之间的关系。