AT_code_formula_2014_final_g ノイハの塔

有一个著名的益智游戏叫做「汉诺塔」。汉诺塔由 $3$ 根柱子和 $N$ 个大小各不相同、中央有孔的圆盘组成。三根柱子编号为 $1$ 到 $3$。第 $i$ 小的圆盘半径为 $i$ 厘米。 最开始，所有圆盘都按照从大到小的顺序堆叠在柱子 $1$ 上，形成一个“塔”。柱子 $2$ 和 $3$ 上没有任何圆盘。玩家每次操作可以将某根柱子顶部的圆盘移动到另一根柱子顶部。此时，不能将较大的圆盘放在较小的圆盘上。汉诺塔的目标是用尽量少的操作次数，将高度为 $N$ 的塔移动到柱子 $2$ 或柱子 $3$ 上。 高桥君很久没玩这个游戏了，最近想再次挑战，于是从储藏室里找出了汉诺塔玩具。然而，有人恶作剧，把 $N$ 个圆盘以乱序堆在了柱子 $1$ 上。于是高桥君决定从这个乱序状态开始，不再遵守“不能将较大的圆盘放在较小的圆盘上”的规则，进行操作，将所有圆盘移动到某根柱子（可以是柱子 $1$），使得所有圆盘从下到上按从大到小的顺序堆叠，形成一个新的“塔”，作为另一种玩法。 现在给出初始状态下柱子 $1$ 上圆盘的大小信息，请你给出一种操作方案，将所有圆盘移动到某根柱子（可以是柱子 $1$），使其从下到上按从大到小的顺序堆叠。注意，为了保证玩法的美观，操作次数不得超过 $225,000$ 次。

输入通过标准输入给出： > $N$ > $r_1$ > $r_2$ > $\vdots$ > $r_N$ - 第 $1$ 行是圆盘的数量 $N\ (1\leq N\leq 10,000)$。 - 接下来的 $N$ 行中，第 $i$ 行给出初始状态下从下往上第 $i$ 个圆盘的半径 $r_i\ (1\leq r_i\leq N)$。 - 对于任意 $x\neq y$，有 $r_x\neq r_y$。

输出如下格式： > $M$ > $from_1$ $to_1$ > $from_2$ $to_2$ > $\vdots$ > $from_M$ $to_M$ - 第 $1$ 行输出操作次数 $M$。 - 接下来的 $M$ 行中，第 $i$ 行输出第 $i$ 次操作：将某根柱子顶部的圆盘从 $from_i$ 移动到 $to_i$，用空格分隔。 - 若在第 $i$ 次操作时，柱子 $from_i$ 上没有圆盘，则该操作无效。除此之外的操作均为有效操作。 - 与传统汉诺塔不同，本题允许将较大的圆盘放在较小的圆盘上。 - 仅当 $M\leq 225,000$ 且所有操作均有效，且最终某根柱子上所有圆盘从下到上按从大到小的顺序堆叠时，答案才被判为正确。

### 部分分 本题设有部分分。 - 对于 $1\leq N\leq 400$ 的数据集，答对可得 $30$ 分。 - 对于 $1\leq N\leq 10,000$ 的数据集，答对可再得 $70$ 分，总分为 $100$ 分。 ### 样例解释 1 最初，所有圆盘按逆序堆叠在柱子 $1$ 上。可以依次将顶部圆盘移动到柱子 $2$，这样从下到上就按从大到小的顺序排列了。 ### 样例解释 2 最终所有圆盘堆叠的柱子可以是柱子 $1$。 由 ChatGPT 4.1 翻译