410792: GYM104114 H Hanoi

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.

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

The second line of the input contains $$$n$$$ integers $$$p_1, p_2, \ldots, 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, \ldots, p_n$$$ form a permutation (in other words, each number from $$$1$$$ to $$$n$$$ appears exactly once amongst $$$p_1, p_2, \ldots, p_n$$$).

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

Each of the following $$$k$$$ lines should contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq 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$$$.

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

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 $$$\langle 2, 1 \rangle \langle 4, 3 \rangle \langle 5 \rangle$$$.
• Move $$$4$$$ is legal as the first rod is relaxed. The configuration is $$$\langle 2, 1, 3 \rangle \langle 4 \rangle \langle 5 \rangle$$$.
• After moves $$$5$$$ and $$$6$$$, the configuration is $$$\langle 2, 1 \rangle \langle \rangle \langle 5, 4, 3 \rangle$$$.
• Last moves $$$7$$$, $$$8$$$ and $$$9$$$ determine the final configuration is $$$\langle \rangle \langle \rangle \langle 5, 4, 3, 2, 1 \rangle$$$.