2050 - 汉诺塔

通过次数

21

提交次数

53

时间限制 : 1 秒
内存限制 : 128 MB

汉诺塔是根据一个印度传说形成的数学问题:有三根杆子A, B, C, A杆上有n个穿孔圆盘, 盘的尺寸由下到上依次变小. 要求按照下列规则将所有圆盘移至C杆:

      1. 每次只能移动一个圆盘

      2. 大盘不能叠在小盘上面

找出最少需要移动多少次, 并打印移动的方案。

输入

一个整数n(1<=n<=15), 表示A杆最初有多少个圆盘。

输出

第一行, 输出最少移动的次数.

以下每行分别打印一次移动(例如, 移动A杆最上面的圆盘到C杆, 则输出"Move A to C")。

样例

输入

3

输出

7
Move A to C
Move A to B
Move C to B
Move A to C
Move B to A
Move B to C
Move A to C

提示

【样例解释】

15792247797465.png

【数据规模】

50% 的数据,满足 1≤n≤5;

100%的数据,满足 1≤n≤15。