問題文
有一个名为“河内塔”的著名益智游戏。 河内塔是由 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 也很好。