3909双塔问题

3909   双塔问题

题目描述

楚继光:“防御系统还真有用,修罗王的魔法炮阵的火力果然减弱了,但好像还差一点点啊?”

墨老师:“哦,是吗,那试试双塔防御体系吧。”

如图所示,给定A,B,C三根足够长的细柱,在A柱上放有2n个中间有空的能量圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的,图为n=3的情形。现要将这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。每次只能移动一个圆盘,每个柱子的圆盘保持上小下大的顺序。要求输出最少移动次数。


输入格式:

输入为一个正整数,表示A柱上有2n个圆盘。

输出格式:

输出仅一行,包含一个正整数,为最少移动次数。
输入样例 复制
2
输出样例 复制
6

说明

对于50%的数据, 1<=n<=25 
对于100% 数据, 1<=n<=200
14
33
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型递推
难        度