在衡中,众所周知,所有的电子设备是一律禁物。但是总是有小强以身犯险,atttx123很荣幸的成为其中的一员。在每天13个小时的埋头苦学之后,他总要抽出一点点时间在被窝里搞自己的电子词典,小强atttx123很强悍地依然去玩那HANOI(汉诺塔),话说他玩了很长很长时间了呢……
对于汉诺塔问题,大家一定很熟悉。给定A,B,C三根足够长的细柱,在A柱上放有n个中间有圆孔的圆盘,且从下向上半径依次减小,共有n个不同的尺寸(下图为n=4的情形)。现要将 这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。
因为他的电子词典的特殊性,这个游戏要有新的要求:
(1) 每次光标只能移动一下,且只能移动到相临的柱子上;
(2) 光标从A柱上向左移动则到达C柱,从C柱上向右移动则到达A柱;
(3) 当某个盘子被选择之后计数器开始计数,此后每移动光标一次步数加一(盘子不跟随光标移动),当光标到达目标位置释放后盘子直接到达目标位置,计数器停止计数,故不用考虑光标移动过程中每个柱子上盘子的大小次序问题的;
(4)A、B、C三根细柱上的圆盘都要保持上小下大的顺序(释放以后);
(5)最终计数器的显示数就为移动的步数;
atttx123很喜欢玩这个游戏,以至于要立志每天玩完1盘,他的电子词典向右移动按钮失灵了(谁叫他光玩呢—↓—),于是他想正常的Hanoi塔游戏对于n个盘则最少步数为2^n-1,那么只用向左移动键玩,则对于n个盘最小步数是多少?
他要估计自己玩完一盘到底要多少时间~~~~~。
【数据范围】
0<=30%<=30
0<=100%<=1000
样例解释
1号盘: a===》c (一步)
2号盘: a===》b (两步)
1号盘: c===》b (一步)
3号盘: a===》c (一步)
1号盘: b===》a (一步)
2号盘: b===》c (两步)
1号盘: a===》c (一步)
共:1+2+1+1+1+2+1=9步
输入为一个整数n (0≤n≤1000),表示在A柱上放有n个圆盘。
输出仅一行,包含一个整数,为完成上述任务所需的最少移动次数An(保证 An≤10 ^1000)。