No.397 NO MORE KADOMATSU
タグ : / 解いたユーザー数 192
作問者 : koyumeishi / テスター : btk
問題文
門松列 とは $3$ 個の要素からなる数列 $A_1, A_2, A_3$ で以下の 2 つの条件を満たすものです。
- $A_1, A_2, A_3$ は全て異なる
- $3$ つの要素の中で $A_2$ が最も大きい,または,$A_2$ が最も小さい
先日の門松列コンテストが不評だったので、門松列をぶち壊します。
長さ $N$ の数列 $A$ が与えられます。
あなたは
- $A$ の $u$番目の要素と $v$番目の要素を入れ替える ($0 \leq u,v < N$ , $u \neq v$)
この操作を繰り返して、 $A$ の連続部分列に門松列を含まないようにしてください。
操作後の $A$ に $A_i, A_{i+1}, A_{i+2}$ が門松列となるような $i$ が存在すると不正解となります。
クエリ数が見えると面白いかもと思ったので、リアクティブ問題になっています。 入出力の項を注意して読んでください。
入力
$N$ $A_0$ $A_1$ ... $A_{N-1}$ $Dummy$
1 行目に数列の長さ $N$ 、 2 行目に$A$の各要素が空白区切りで与えられます。
3 行目の入力はリアクティブジャッジ用のダミー入力です。 解答を出力した後に受け取ってください。
(受け取らなくても通るかも知れませんが、念のため)
入力は全て整数で、以下の制約を満たします。
$3 \leq N \leq 100$
$1 \leq A_i \leq 100$
$Dummy = -1$
出力
$M$ $u_0$ $v_0$ $u_1$ $v_1$ $\vdots$ $u_{M-1}$ $v_{M-1}$
1 行目に操作の回数、 2 行目以降に 1 行ずつに i 回目の操作の $u$,$v$ ($0 \leq u,v < N$ , $u \neq v$)
を出力してください。
最後に標準出力の flush をしてください。
特に交換回数に制限はありませんが、あまりに多いとジャッジ側が TLE するかもしれません。
サンプル
サンプル1
入力
3 1 3 2 -1
出力例
2 0 1 1 2
出力の一例です。
[1,3,2] -> [3,1,2] -> [3,2,1] となり、連続部分列に門松列を含まなくなります。
0-indexed であることに留意してください。 また、ダミー入力は解答出力後に受け取ってください。
サンプル2
入力
6 1 3 2 2 3 1 -1
出力例
1 1 5
[1,3,2,2,3,1] -> [1,1,2,2,3,3]
サンプル3
入力
10 1 2 3 4 5 6 7 8 9 10 -1
出力例
0
元々門松列を含まないので交換回数はゼロでも大丈夫です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。