Canadian Computing Olympiad: 2017 Day 2, Problem 3
You are given a rectangular grid of numbered tiles, with no empty spaces. This grid can only be manipulated using a sequence of shift operations. A shift involves either moving an entire row left or right by some number of units, or moving an entire column up or down by some number of units. Tiles which move outside of the rectangular boundaries wrap around to the opposite side of the grid. For example, in the grid
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
a vertical shift downwards by one applied to the second column has the following result:
0 13 2 3
4 1 6 7
8 5 10 11
12 9 14 15
Notice that a left shift by
In a grid with
You may have noticed that in the first example given above, the tiles are in a very organized
formation. We call such arrangements solved. That is, a grid of tiles is solved when the first row
contains the numbers from
Find a sequence of shift operations that restores a scrambled grid to a solved state.
Input Specification
The first line will contain two space-separated integers
Note that both
For 5 of the available 25 marks,
For an additional 10 of the available 25 marks, the puzzle is solvable in at most 2 moves.
Output Specification
Output any sequence of moves that solves the puzzle, in the following format:
- The first line of output should contain a single integer
, representing the number of moves in the sequence. - The next
lines should be either of the form 1 representing a right shift of the row by , or of the form 2 representing a down shift of the by .
Sample Input 1
2 4
4 2 3 0
1 5 6 7
Output for Sample Input 1
2
2 1 1
1 1 1
Explanation for Output for Sample Input 1
We shift the first column down by one to obtain
1 2 3 0
4 5 6 7
then shift the first row right by one to reach the state
0 1 2 3
4 5 6 7
which is solved.
Sample Input 2
4 2
2 3
5 0
4 1
6 7
Output for Sample Input 2
7
1 1 1
2 1 1
1 2 1
1 3 1
2 1 2
1 1 1
2 1 1
Explanation for Output for Sample Input 2
The sequence of shifts, starting from the input is:
2 3 3 2 6 2 6 2 6 2 1 2 2 1 0 1
5 0 -> 5 0 -> 3 0 -> 0 3 -> 0 3 -> 4 3 -> 4 3 -> 2 3
4 1 4 1 5 1 5 1 1 5 6 5 6 5 4 5
6 7 6 7 4 7 4 7 4 7 0 7 0 7 6 7
Comments
Equivalent to this problem.