← 返回题目列表

AtCoder · code_formula_2014_final_g

G. 诺伊哈之塔

中文机器翻译题面 查看原题

問題文

有一个名为“河内塔”的著名益智游戏。 河内塔是由 3 根柱子以及中心有孔、大小不同的 N 个圆盘组成的益智游戏。 3 根桩上标有 1 我决定将所有值添加到 3 号。此外,第 i 小的圆盘半径是 i 是厘米。

一开始,所有的圆盘按照从下到上的顺序、尺寸从大到小地堆放在桩上,形成“塔”。 1 上没有放任何东西。 2, 3 钳子是 1 在一次操作中,可以将某根柱子塔顶上的圆盘移动到另一根柱子上,并堆放到目标柱子的塔顶。 此时,小的圆盘上不能放置大的圆盘。 河内塔的目标是在尽可能少的操作次数内,将高度N的塔移动到柱子 2 或柱子 3 上。

高桥君想久违地玩这个拼图,于是从壁橱深处找出了河内塔玩具。 但是,好像有人捣乱,N 所有圆盘都以杂乱的顺序堆放在柱子 1 上。 于是高桥君决定从那个杂乱的状态开始,不遵守“不能把大的圆盘放在小圆盘上”的规则操作,玩一个别的拼图——把所有圆盘移动到某根柱子上,使它们按照尺寸从下到上依次堆放。

事先,会提供堆放在柱子上的圆盘尺寸信息, 1 请将所有圆盘移动到任意一个柱子(任意一个柱子即可),使其按尺寸顺序堆叠。 1 请给出一种移动操作的方法。 225,000 但是,如果操作过多,作为拼图就不美观了,


入力

输入是从标准输入按以下格式给出的

N
r_1
r_2
:
r_N
  • 1 请在规定的次数内完成移动操作。 N (1 ≦ N ≦ 10,000) 被给予。
  • 2 从线 N 行数过多 i 行表示圆盘的数量。 1 行表示,最初在柱子上的圆盘顺序从下往上计算。 i 行表示放置在柱子第几层的圆盘编号。 r_i (1 ≦ r_i ≦ N)被给予。
  • x ≠ y 如果是的话, r_x ≠ r_y 成立。

部分点

针对此问题设置了部分分数。

  • 1 ≦ N ≦ 400 对于满足条件的数据集给出正确答案时, 30 点。
  • 1 ≦ N ≦ 10,000对于进一步满足条件的数据集会额外 70 得到分数。总计为100分。

出力

输出格式如下。

M
from_1 to_1
from_2 to_2
:
from_M to_M
  • 1 行表示操作次数。 M 。
  • 2 从线 M 行数过多 i 在线i第几次操作中移动的圆盘原来的柱编号 from_i 和移动到的柱编号 to_i 用空格分隔输出。
  • i 第几次操作时,如果柱 from_i 上没有圆盘,则该操作不适用。其他操作视为适用。
  • 与原来的河内塔不同,需要注意允许将较大的圆盘放在较小的圆盘上。
  • M ≦ 225,000 并且只有所有操作都正确,最终所有圆盘按从下到上由大到小堆叠在某一柱上时,答案才被认为是正确的。

入力例1

5
1
2
3
4
5

出力例1

5
1 2
1 2
1 2
1 2
1 2

起初,所有圆盘按逆序堆叠在柱 1 上。从上到下依次移动到柱 2 上,可以按从下到上的顺序重新排列成从大到小。


入力例2

5
5
3
2
4
1

出力例2

8
1 2
1 2
1 3
1 3
2 1
3 1
3 1
2 1

最终所有圆盘堆叠的柱是 1 也很好。