Hanoi （ 2022 ICPC Southeastern Europe Regional Contest ）

Hanoi （ 2022 ICPC Southeastern Europe Regional Contest ）

The original problem “Towers of Hanoi” is about moving $n$ circular disks of distinct sizes between $3$ rods. In one move, the player can move only the top disk from one rod to the top of another. The disks should always be placed one over the other in decreasing order of sizes. Initially, the $n$ disks reside on rod $1$ and the goal is to have them all $n$ reside on rod $3$.

There is a myth of an Indian temple where priests are solving the instance of “Towers of Hanoi” with $64$ disks since the beginning of time. It is believed that once this instance is solved, the world will end.

However, this “Relaxed Hanoi” problem is not that apocalyptic. In fact, it is pretty optimistic as once you correctly solve it, you will get a positive verdict. In this variation, rod $1$ is not subject to the order rule. In other words, the disks on rod $1$ can reside in any order at any point of time.

For an instance of the “Relaxed Hanoi” problem, provide at most $2\cdot n^2$ moves that solve the problem.

Input

The first line of the input contains a single integer $n$ ($1\le n\le 500$) — the number of disks.

The second line of the input contains $n$ integers $p_1,p_2,\dots ,p_n$ — the sizes of the disks on rod $1$ from bottom to top (the first is the bottom disk and the $n$-th is the top disk).

It is guaranteed that $p_1,p_2,\dots ,p_n$ form a permutation (in other words, each number from $1$ to $n$ appears exactly once amongst $p_1,p_2,\dots ,p_n$).

Output

The first line of output should contain a single integer $k$ ($0\le k\le 2\cdot n^2$) — the number of moves.

Each of the following $k$ lines should contain two integers $a_i$ and $b_i$ ($1\le a_i,b_i\le 3$), describing a move of the topmost disk from rod $a_i$ to rod $b_i$.

In the end, all $n$ disks should reside on rod number $3$.

Example

Input

5
2 1 5 3 4

Output

9
1 2
1 2
1 3
2 1
2 3
1 3
1 2
1 3
2 3

Note

The provided output has only $9$ moves. For $n=5$, any solution with at most $50$ moves will suffice.

• After moves $1, $ 2 and $3$, the configuration is $⟨2,1⟩⟨4,3⟩⟨5⟩$.
• Move $4$ is legal as the first rod is relaxed. The configuration is $⟨2,1,3⟩⟨4⟩⟨5⟩$.
• After moves $5$ and $6$, the configuration is $⟨2,1⟩⟨⟩⟨5,4,3⟩$.
• Last moves $7$, $8$ and $9$ determine the final configuration is $⟨⟩⟨⟩⟨5,4,3,2,1⟩$.

题面描述

问题背景: 经典的汉诺塔问题涉及将 $n$ 个大小不同的圆盘在 $3$ 根柱子之间移动。每次只能移动最上面的一个圆盘，并且任何时候都必须保持圆盘按大小递减的顺序叠放。初始时，所有圆盘都在柱子 $1$ 上，目标是将它们全部移动到柱子 $3$ 上。

问题变种: 在这个“Relaxed Hanoi”问题中，柱子 $1$ 不受顺序规则的限制。也就是说，柱子 $1$ 上的圆盘可以以任意顺序叠放。

任务: 对于给定的“Relaxed Hanoi”问题实例，提供一个最多包含 $2\cdot n^2$ 步的移动序列，将所有圆盘从柱子 $1$ 移动到柱子 $3$。

输入:

• 第一行包含一个整数 $n$ ($1\le n\le 500$)，表示圆盘的数量。
• 第二行包含 $n$ 个整数 $p_1,p_2,\dots ,p_n$，表示柱子 $1$ 上从下到上的圆盘大小。保证这些整数是 $1$ 到 $n$ 的一个排列。

输出:

• 第一行输出一个整数 $k$ ($0\le k\le 2\cdot n^2$)，表示移动的步数。
• 接下来的 $k$ 行每行包含两个整数 $a_i$ 和 $b_i$，表示将柱子 $a_i$ 最上面的圆盘移动到柱子 $b_i$。

示例:
输入:

5
2 1 5 3 4

输出:

9
1 2
1 2
1 3
2 1
2 3
1 3
1 2
1 3
2 3

题解

问题分析:

• 由于柱子 $1$ 不受顺序规则的限制，我们可以利用这一点来简化移动过程。
• 目标是将所有圆盘从柱子 $1$ 移动到柱子 $3$，并且最终柱子 $3$ 上的圆盘必须按大小递减的顺序叠放。

解题思路:

1. 初始化: 将所有圆盘从柱子 $1$ 移动到柱子 $3$，但保持柱子 $3$ 上的圆盘按大小递减的顺序。
2. 移动策略:
   • 使用一个辅助柱子（柱子 $2$）来临时存放圆盘。
   • 当柱子 $1$ 上的圆盘大小小于当前柱子 $3$ 上的最小圆盘时，直接将其移动到柱子 $3$。
   • 否则，将柱子 $3$ 上的较小圆盘移动到柱子 $1$，腾出空间，然后再将较大的圆盘移动到柱子 $3$。
3. 复杂度: 由于每个圆盘最多需要 $2n$ 步移动，总步数不会超过 $2n^2$。

代码分析

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
set<int> st[3];void solved()
{int n;cin >> n;vector<int> arr(n + 1, 0);for (int i = 1; i <= n; i++){cin >> arr[n - i + 1];  // 反转输入顺序，方便处理}vector<array<int, 2>> ans;int start = 3;set<int> st2;for (int i = 1; i <= n; i++){if (st2.empty()){st2.insert(arr[i]);ans.push_back({1, start});  // 直接将圆盘移动到柱子3}else{int v = *(st2.begin());if (v >= arr[i]){st2.insert(arr[i]);ans.push_back({1, start});  // 直接将圆盘移动到柱子3}else{ans.push_back({1, 2});  // 将圆盘移动到柱子2vector<int> path;while (!st2.empty() && *(st2.begin()) < arr[i]){path.push_back(*(st2.begin()));ans.push_back({start, 1});  // 将柱子3上的较小圆盘移动到柱子1st2.erase(st2.begin());}st2.insert(arr[i]);ans.push_back({2, 3});  // 将圆盘移动到柱子3for (int j = 0; j < path.size(); j++){st2.insert(path[j]);ans.push_back({1, 3});  // 将柱子1上的圆盘移动到柱子3}}}}cout << ans.size() << endl;for (auto [i, j] : ans){cout << i << " " << j << endl;}
}signed main()
{close;solved();
}

代码分析:

• 输入处理: 读取圆盘数量 $n$ 和圆盘大小数组 $arr$，并将数组反转以便从顶部开始处理。
• 移动策略:
  • 使用 st2 集合来维护柱子 $3$ 上的圆盘大小。
  • 对于每个圆盘，如果它小于或等于柱子 $3$ 上的最小圆盘，则直接移动到柱子 $3$。
  • 否则，将柱子 $3$ 上的较小圆盘移动到柱子 $1$，腾出空间后再将当前圆盘移动到柱子 $3$。
• 输出: 输出移动步数和每一步的移动操作。

复杂度分析:

• 每个圆盘最多需要 $2n$ 步移动，因此总步数不会超过 $2n^2$，满足题目要求。

总结

该问题通过放松柱子 $1$ 的顺序规则，简化了汉诺塔问题的移动过程。通过合理的移动策略，可以在 $2n^2$ 步内将所有圆盘移动到目标柱子。代码实现中使用了集合来维护柱子 $3$ 上的圆盘大小，并通过临时移动较小圆盘来腾出空间，确保最终柱子 $3$ 上的圆盘按大小递减的顺序叠放。