31203번 - Square Grid Puzzle 점수다국어

문제

In this puzzle, you are given a 0ドル$-indexed $N \times N$ square grid consisting of distinct integers from 0ドル$ to $N \times N - 1,ドル inclusive. Your goal is to reach the ordered state where the number at the intersection of the $i$-th row and the $j$-th column is equal to $i \times N + j$ for each 0ドル ≤ i, j < N$. You can achieve this goal using two types of moves:

• Down move: "D $a[0]$ $a[1]$ $\dots$ $a[N - 1]$", where $a[0],ドル $a[1],ドル $\dots,ドル $a[N - 1]$ is some rearrangement of the numbers from the topmost row of the grid. With this move, the topmost row is removed and the new row created with the numbers $a[0],ドル $a[1],ドル $\dots,ドル $a[N - 1]$ from left to right is added to the bottom of the grid.
• Right move: "R $b[0]$ $b[1]$ $\dots$ $b[N - 1]$", where $b[0],ドル $b[1],ドル $\dots,ドル $b[N - 1]$ is some rearrangement of the numbers from the leftmost column of the grid. With this move, the leftmost column is removed and the new column created with the numbers $b[0],ドル $b[1],ドル $\dots,ドル $b[N - 1]$ from top to bottom is added to the right of the grid.

Rearrangement refers to changing the order of the numbers without adding or removing any of them, and it may preserve the original order.

For example, if the current grid is:

By performing the move "D 6ドル$ 2ドル$ 4ドル$", we will obtain the following grid:

However, if we instead execute move "R 2ドル$ 8ドル$ 7ドル$", we would get:

For $N = 3,ドル the target grid would look like this:

You aim to solve the puzzle with fewer than 3ドル \times N$ moves. However, partial points may be awarded in case you use more moves or not solve the puzzle. Refer to the scoring section for details.

입력

The first line contains a single integer: $N$.

The following $N$ lines describe the initial grid, with $N$ numbers on each line.

출력

The first line should contain a single integer, $M,ドル the number of moves. Each of the following $M$ lines should contain a single move.

제한

• 2ドル ≤ N ≤ 9$
• There is an equal number of cases for each $N$ from 2ドル$ to 9ドル$.

점수

Let’s denote $M$ as the amount of moves in your solution. Additionally, define $A = 3 \times N$ and $B = 2 \times N^2$.

If your output is invalid, or if $M > B,ドル you receive 0ドル$ points. Otherwise, your score depends on the amount of numbers in the correct target positions (denoted as $C$).

If $C < N \times N$ the puzzle is not solved and you will only receive $\left(50 \times \frac{C}{N \times N} \right)\%$ of points for a test. Otherwise:

• If $M < A,ドル you will receive 100ドル\%$ of points for a test.
• If $A ≤ M ≤ B,ドル you will receive $\left(40 \times \left(\frac{B-M}{B-A}\right)^2 + 50\right)\%$ of points for a test.

Each individual test is worth the same number of points. Your score is the sum of individual test scores, and your final score will be the best score among all submissions.

힌트