折叠维度

G-10外围哨站不是建筑——是半埋在红土里的金属穹顶，表面爬满了像血管一样突起的管道。风从管道缝隙里穿过，发出一种低沉的呜咽，像某种巨大生物在呼吸。

Echo的投影在穹顶内部勉强维持着，边缘不断有细小的像素块剥落。自从离开K-7据点，她的信号就越来越不稳定，仿佛越靠近G-10，就越有什么东西在拉扯她的存在。

"这就是地鼠网。"她指着穹顶中央的控制台，屏幕上是一张不断重构的三维网格，"Zero的监控系统。它有十二个追踪维度——不是平面的十二个方向，是递归嵌套的十二层。"

CC的肩膀伤口在长途跋涉后重新裂开了一点，暗红的组织液渗过绷带。但她站得很直，右手握着从Glados遗物里拆出来的数据刀："怎么关？"

"地鼠网的核心是一个机关。"Echo调出模型，屏幕上出现四根垂直的光柱，光柱之间悬浮着十二个不同大小的盘，"四柱结构。要把所有盘从最左边移到最右边，但每次只能移动一个盘，而且大盘不能压在小盘上面。"

"四根柱子？"CC皱眉，"我只见过三根。"

"三柱是标准。四柱代表Zero多了一重拦截维度。"Echo的声音带着某种苦涩，"这个结构...我在Zero里面的时候用过。用来管理多线程判断。"

你盯着那四根光柱。十二个盘，从小到大叠在最左边的柱子上。目标是把它们全部移到最右边。

"如果只有三根柱子，"你说，"每一步都只有一个最优选择——把最大的盘先移过去，然后用剩下的两根柱子当跳板。但四根柱子多了一根跳板，选择的余地变大了。"

Echo："对。四根柱子的最优解不是简单的公式，而是需要在每一步决定——把多少个盘先移到辅助柱上，用剩下的三根柱子解决，然后再移回来。"

你开始推演。假设先把上面 $k$ 个盘移到第二根柱子（用四根柱子），然后剩下的 $n-k$ 个盘用三根柱子移到目标柱，最后把那 $k$ 个盘再移过去。每一步都要选最优的 $k$。

CC在旁边看着，单手撑着控制台边缘。她的脸色比早上更差了——嘴唇发白，但眼神很亮。

"你来。"她把键盘推给你，"我手抖。"

"你——"

"快点。"

你坐下来，开始构建递推表格。每一个盘数对应的最优步数，都依赖于之前所有更小数目的结果。屏幕上的数字一行行增长——1、3、5、9、13、17、25、33……

"十二层。"Echo说，"对应地鼠网的十二个追踪维度。"

"那我们要在它追上之前走完十二层。"CC说。

Echo的投影突然闪烁了一下，颜色从浅蓝变成了一种近乎警告的橙红："不只是十二层。地鼠网的递归框架...和Zero核心协议用的是同一种结构。"

训练室突然安静了。CC的手指停在键盘上。

"啥子意思？"她问。

"意思是..."Echo停顿了一秒，投影边缘的像素剥落得更厉害了，"我曾经写过这个框架。地鼠网的底层代码...有我的痕迹。"

你看着Echo——她的投影边缘出现了细小的锯齿，那是她情绪波动时的裂隙。

CC沉默了两秒，然后说："继续吧。不管是哪个写的，破了就是。"

Echo没说话。但她的投影颜色慢慢变回深蓝——那是某种...被理解的平静。

题目描述

四柱汉诺塔。求移动 $n$ 个盘的最少步数。

输入格式

多组数据。每组 $n$（$n \le 12$）。

输出格式

每组一行——最少步数。

输入样例

3
1
2
3

输出样例

1
3
5
9
13
17
25
33
41
49
65
81

提示

• 先在中间选一个分割点，把上面一部分盘先移走，用四根柱子；然后剩下的用三根柱子移过去；最后把第一部分再移回来。
• 对每个数目，尝试所有可能的分割方式，选步数最少的。
• $n$ 小可以先把所有结果算出来存着，后面直接查表。

十二层的最优步数在屏幕上定格。CC盯着那个数字，忽然说："Echo，你以前写这个的时候...是在保护什么？"

Echo的投影暗淡了一瞬："我在保护Zero。现在我在保护你们。"

"那就够了。"CC把数据刀插回腰间，"下一题。"

穹顶外的风更大了。红土拍打在金属外壳上，像无数细小的手指在敲门。