/ Vijos / 题库 /

4-Hanoi-Tower

4-Hanoi-Tower

描述

“汉诺塔”,是一个众所周知的古老游戏。现在我们把问题稍微改变一下:如果一共有4根柱子, 而不是3根,那么至少需要移动盘子多少次,才能把所有的盘子从第1根柱子移动到第4根柱子上呢?

为了编程方便,您只需要输出这个结果mod 10000的值。

格式

输入格式

一个正整数n。(0<n<=50000)

输出格式

一个正整数,表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。

样例1

样例输入1

2

样例输出1

3

限制

来源

huyichen

信息

ID
1073
难度
4
分类
动态规划 点击显示
标签
(无)
递交数
2315
已通过
967
通过率
42%
上传者