## CCO '17 P6 - Shifty Grid

View as PDF

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 units is the same a right shift by units. Similarly, an upward shift by units is a downward shift by units. Thus, without loss of generality, we will restrict the shift directions to be only to the right or down.

In a grid with rows and columns, there are tiles in total. You may assume that the tiles are numbered with distinct integers from to .

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 to in order, the second row has the numbers from to in order, and so on, with the last row having the number to in order.

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 and (). The next lines will contain space-separated integers, representing the grid.

Note that both and will always be even, and there will be a solution requiring at most shift operations.

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