問題一覧 > 通常問題

No.366 Robot Sort

レベル : / AI推定難易度 : 925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 258
作問者 : 🍡yurahuna / テスター : btk
お気に入りにしたユーザー ProblemId : 1077 / 自分の提出
問題文最終更新日: 2026-06-25 07:41:08
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 136 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。