問題一覧 > 通常問題

No.397 NO MORE KADOMATSU

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 192
作問者 : koyumeishikoyumeishi / テスター : btkbtk
1 ProblemId : 1233 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-07-11 18:01:46

問題文

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