No.366 ロボットソート
タグ : / 解いたユーザー数 241
作問者 :
🍡yurahuna
/ テスター :
btk
問題文
ロボットのYURAHUNA君は、工場でブロックを並び替える仕事をしています。
今、YURAHUNA君の目の前のテーブルには $N$ 個のブロックが横一列に並んでいます。ブロックの長さは左から順にそれぞれ $a_1, a_2, ..., a_N$ です。
YURAHUNA君はこれらのブロックを、左から見て長さの小さい順になるように並び替えなければなりません。
YURAHUNA君の手はコの字型で幅が $K$ なので、YURAHUNA君にできるのは「左から $i$ 番目のブロックと左から $i + K$ 番目のブロックを入れ替える」という操作のみです。
（ただし、$i$ $(1 \leq i \leq N)$ を決めたとき、$i + K$ 番目のブロックが存在しなければ操作を行うことはできません。）
さて、YURAHUNA君は最小何回の操作でブロックを並び替えることができるでしょうか？
入力
$N$ $K$ $a_1$ $a_2$ ... $a_N$
- 1行目には、ブロックの個数 $N$ $(1 \leq N \leq 1000)$ とYURAHUNA君の手の幅 $K$ $(1 \leq K \leq 1000)$ の値がスペース区切りの整数で与えられる。
- 2行目には、ブロックの長さ $a_i$ $(1 \leq i \leq N, 1 \leq a_i \leq 10 ^ 9)$ がスペース区切りの整数で与えられる。
$a_i$ は左から $i$ 番目のブロックの長さを表す。 - ブロックの長さはすべて異なる。すなわち、すべての $i, j$ $(1 \leq i < j \leq N)$ について、$a_i \neq a_j$ である。
出力
YURAHUNA君がブロックを並び替えるのにかかる最小の操作回数を1行で出力してください。
もし並び替えが不可能な場合は、-1を出力してください。
最後に改行してください。
サンプル
サンプル1
入力
6 2 8 6 5 3 1 10
出力
4
1番目と3番目、2番目と4番目、3番目と5番目, 1番目と3番目の順にブロックを入れ替えると、左から見て長さの小さい順に並び替えることができます。これは操作回数が最小となる並び替え方です。
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
サンプル2
入力
4 3 5 7 2 11
出力
-1
どのように操作しても、左から見て長さの小さい順に並び替えることはできません。
なお、この例ではYURAHUNA君は1番目と4番目のブロックを入れ替えることしかできないことに注意してください。
サンプル3
入力
5 10 1 2 3 5 8
出力
0
YURAHUNA君の手はこれらのブロックを並び替えるには大きすぎますが、ブロックは既に左から見て長さの小さい順に並んでいるので、YURAHUNA君は1回も操作を行わなくてよいです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。