New Year's '18 P5 - Hanoi Heuristics

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.5s
Memory limit: 256M

Problem types

The Tower of Hanoi consists of N disks arranged in three piles numbered 1, 2, and 3. The disks all have distinct sizes, with disk 1 being the smallest and disk N being the largest. Larger disks cannot be placed on top of smaller disks. An arrangement of the disks can thus be represented uniquely by a sequence of N digits, each being 1, 2, or 3, such that the i^\text{th} digit represents the pile where disk i is located.

A legal move consists of taking a single disk from the top of one pile, and placing it at the top of a different pile, such that the result is a valid arrangement. That is, a larger disk cannot be placed on top of a smaller disk. A move can be represented by two integers a and b, where the corresponding move takes the disk at the top of pile a and places it at the top of pile b.

Initially, all disks are in pile 1. You are given Q distinct arrangements, and must find a sequence of legal moves that visits all Q arrangements, in any order. It is permitted to visit an arrangement more than once. The sequence does not need to be optimal. However, it can have at most C moves.


C = 2\,000\,000

1 \le N \le 15

1 \le Q \le 20\,000

The Q arrangements are distinct.

Subtask 1 [20%]

N \le 13

Subtask 2 [20%]

Q \le 50

Subtask 3 [50%]

Q \le 7\,000

Subtask 4 [10%]

No additional restrictions.

Input Specification

The first line contains two space-separated integers N and Q.

The next Q lines each contain a string of N digits, representing the arrangements to be visited.

Output Specification

The first line of output should contain an integer K, the number of moves. Recall that K may be at most C.

The next K lines should each contain two integers a and b, representing a legal move.

Sample Input

3 2

Sample Output

1 2
1 3
2 1
1 3
1 2
3 1


There are no comments at the moment.