No.3775 Distant Swap
Rapca1256
aogera
p-adic
tomorunn問題文
正の整数 $K$ と、$N$ 以下の正の整数の並び替え $P=(P_1,P_2,\cdots,P_N)$ が与えられます。
次の操作を $0$ 回以上行うことで $P$ を昇順にすることが可能か判定し、
可能な場合は必要な操作回数の最小値を求め、操作回数が最小になるときの操作手順の一例を示してください。
- $1 \le i < j \le N, j - i = K$ なる整数 $i, j$ を選び、$P_i$ と $P_j$ を入れ替える。
入力
$N\ K$ $P_1\ P_2\ P_3\ \cdots \ P_N$
入力は以下の制約を満たします。
- 入力はすべて整数
- $2 \le N \le 1000$
- $1 \le K \le N-1$
- $P$ は $N$ 以下の正の整数の並び替え
出力
操作を $0$ 回以上行うことで $P$ を昇順に並び替えることができない場合は $1$ 行目に-1と出力してください。
できる場合は、$1$ 行目に必要な操作回数の最小値 $m$ を出力してください。
また、$1 \le m$ のとき、$1 \le k \le m$ について、$k$ 回目で $P_i$ と $P_j$ を入れ替える( $i < j$ )なら、$k+1$ 行目に $i,j$ をこの順に半角空白区切りで出力してください。
操作方法が複数存在する場合、どれを出力しても正解と判定されます。
また、最後に改行してください。
サンプル
サンプル1
入力
5 2 5 4 1 2 3
出力
3 2 4 1 3 3 5
$1$ 回目に $P_2,P_4$ を入れ替えることで、$P$ は $(5,2,1,4,3)$ となります。
$2$ 回目に $P_1,P_3$ を入れ替えることで、$P$ は $(1,2,5,4,3)$ となります。
$3$ 回目に $P_3,P_5$ を入れ替えることで、$P$ は $(1,2,3,4,5)$ となります。
$2$ 回以下の操作で $P$ を昇順にすることはできないため、$3$ が答えです。
サンプル2
入力
5 2 5 4 1 3 2
出力
-1
どのように操作を行っても $P$ を昇順にすることはできません。
サンプル3
入力
10 3 1 2 3 4 5 6 7 8 9 10
出力
0
初めから昇順に並んでいる場合もあります。
サンプル4
入力
10 3 10 2 3 1 5 6 7 8 9 4
出力
4 1 4 7 10 4 7 7 10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。