CF98D Help Monks

在一个遥远的王国里，有著名的 Lio Shan 修道院。很久以前，众神在修道院的草坪上建造了三根钻石柱。众神还在其中一根柱子上放了 $n$ 个黄金圆盘，这些圆盘的直径各不相同，并且按照直径从大到小自下而上依次摆放。另外，众神命令要按照以下规则将所有圆盘从第一根柱子移动到第三根柱子： - 每次只能移动一个圆盘； - 不能把较大的圆盘放在较小的圆盘上面。 关于众神旨意完成之后会发生什么，并没有统一的说法：一些人承诺世界和平和永恒幸福，而其他人则预言王国将面临共……（咳，我又扯远了）——末日降临。然而，众所周知，不可能用少于 $2^{n}-1$ 步完成此任务，而懒惰的 Lio Shan 修道士们根本就未曾开始过，因此大家都平静地生活着，也不担心末日降临。然而，最近修道院的状况不佳，智慧的住持 Ku Sean Sun 被迫把一些圆盘的边削掉，并将黄金用于更大的善事。你不觉得住持有权享受空调系统吗？况且一年到头呆在修道院也太无聊了，有时也该尝试点新东西，比如去滑雪……Ku Sean Sun 过了一段时间才意识到自己的大错：边缘被削后，有些圆盘的直径变得相同了，这就使得原本某些无法进行的移动变得可能（因为众神并未禁止把直径相同的圆盘叠放在一起）。因此，末日可能比众神最初设想的提早到来。甚至可能早到 Ku Sean Sun 还没来得及滑雪或吹空调。 聪明的住持绝不让此事发生，便请求一位年迈而睿智的女巫 PikiWedia 帮忙。也许她能算出当前情形下完成众神使命所需的最少步数。但是女巫占卜之后也查不出答案。于是他又请你来帮忙。 给定盘子的数量和各自的直径，你能找出完成众神这个问题所需的最少步数吗？注意：允许把直径相同的圆盘叠在一起，但在最后，第三根柱子上的圆盘顺序必须与最初第一根柱子上一致。

第一行一个整数 $n$，表示圆盘数量（$1\leq n \leq 20$）。 第二行包含 $n$ 个整数 $d_i$，依次表示 Ku Sean Sun 削边之后的圆盘直径。直径从下到上给出（$1\leq d_i \leq 20$，并且对任意 $1\leq i < n$，都有 $d_i \geq d_{i+1}$）。

第一行输出一个整数 $m$，表示完成任务所需的最少移动步数。 接下来 $m$ 行，每行输出两个用空格分隔的正整数 $s_i$ 和 $t_i$，分别代表每步将圆盘从第 $s_i$ 根柱子移动到第 $t_i$ 根柱子（$1\leq s_i,t_i \leq 3$，且 $s_i\neq t_i$）。

注意第三个测试用例说明：最终第三根柱子上的圆盘顺序必须和初始完全一致，即使某些圆盘直径相同。如果不需要保持这个顺序，则可以在更少步数内（仅三步）直接把三块圆盘从第一根柱子搬到第三根柱子。 由 ChatGPT 5 翻译