No.366 Robot Sort
Problem Statement
The robot YURAHUNA works at a factory rearranging blocks.
Right now, on the table in front of YURAHUNA, $N$ blocks are lined up in a horizontal row. The lengths of the blocks, from left to right, are $a_1, a_2, ..., a_N$.
YURAHUNA must rearrange these blocks so that they are in ascending order of length as seen from the left.
Since YURAHUNA's hand is U-shaped with width $K$, the only operation YURAHUNA can perform is "swap the $i$-th block from the left and the $i + K$-th block from the left".
(However, once $i$ $(1 \leq i \leq N)$ is chosen, the operation cannot be performed if the $i + K$-th block does not exist.)
What is the minimum number of operations with which YURAHUNA can rearrange the blocks?
Input
$N$ $K$ $a_1$ $a_2$ ... $a_N$
- The first line contains the number of blocks $N$ $(1 \leq N \leq 1000)$ and the width of YURAHUNA's hand $K$ $(1 \leq K \leq 1000)$ as space-separated integers.
- The second line contains the block lengths $a_i$ $(1 \leq i \leq N, 1 \leq a_i \leq 10 ^ 9)$ as space-separated integers.
$a_i$ represents the length of the $i$-th block from the left. - All block lengths are distinct. That is, for all $i, j$ $(1 \leq i < j \leq N)$, $a_i \neq a_j$.
Output
Output in one line the minimum number of operations YURAHUNA needs to rearrange the blocks.
If the rearrangement is impossible, output -1.
Print a newline at the end.
Sample
Sample 1
Input
6 2 8 6 5 3 1 10
Output
4
By swapping the blocks in the order of the 1st and 3rd, the 2nd and 4th, the 3rd and 5th, and the 1st and 3rd, they can be rearranged into ascending order of length as seen from the left. This rearrangement uses the minimum number of operations.
8 6 5 3 1 10
↓
5 6 8 3 1 10
↓
5 3 8 6 1 10
↓
5 3 1 6 8 10
↓
1 3 5 6 8 10
Sample 2
Input
4 3 5 7 2 11
Output
-1
No matter how the operations are performed, the blocks cannot be rearranged into ascending order of length as seen from the left.
Note that in this example, the only thing YURAHUNA can do is swap the 1st and 4th blocks.
Sample 3
Input
5 10 1 2 3 5 8
Output
0
YURAHUNA's hand is too large to rearrange these blocks, but since the blocks are already in ascending order of length as seen from the left, YURAHUNA does not need to perform any operations.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
🍡yurahuna
btk