3910四塔问题

3910   四塔问题

题目描述

墨老师:“现在可以了吗?”

楚继光:“开始是压制住了修罗王的魔法炮阵,但现在修罗王又加强了火力。”

墨老师:“那就用四塔防御系统好了。”

四塔防御系统一共有4根柱子,而不是3根,那么至少需要移动能量盘多少次,才能把所有的能量盘从第1根柱子移动到第4根柱子上呢?

为了编程方便,你只需输出这个结果%10000的值。

输入格式:

该题含有多组测试数据,每组一个正整数N。(0<N≤50000)

输出格式:

一个正数,表示把N个能量盘从第1根柱子移动到第4根柱子需要的最少移动次数%10000的值。
输入样例 复制
15
输出样例 复制
129

说明

13
19
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型递推
难        度