非負整数 が与えられる。
長さ の数列 を次のように定める。
相異なる 2 つの添字 を選び、 と をともに に置き換える操作を好きな回数行うことができる。
数列のすべての要素を等しくするために必要な操作回数の最小値を求め、その最小値を達成する操作列を 1 つ出力せよ。不可能なら を出力せよ。
可能な場合、与えられた制約のもとで、最小操作回数は常に 回以下であることが証明できる。
この問題には部分点がある。詳しくは Scoring セクションを参照せよ。
入力は次の形式で標準入力から与えられる。
不可能な場合、1 行に を出力せよ。
可能な場合、1 行目に最小操作回数 を出力せよ。続く 行のうち 行目に、 回目の操作で選ぶ 2 つの添字 を次の形式で出力せよ。
各テストケースの得点は、そのテストケースが属するサブタスクの配点に対する割合として、次のように計算される。
すべての要素を等しくすることが不可能な場合:
すべての要素を等しくすることが可能な場合:
各操作について かつ を満たし、出力した 回の操作によって実際にすべての要素を等しくしなければならない。正しい答えが複数存在する場合、どれを出力してもよい。
サブタスクで用いる追加条件は次のとおりである。
追加条件 A
追加条件 B
| 3 | 4 | 추가 조건 A를 만족하고, 이다. |
| 4 | 6 | 추가 조건 A를 만족하고, 이다. |
| 5 | 11 | 추가 조건 A를 만족한다. |
| 6 | 6 | 추가 조건 B를 만족하고, 이다. |
| 7 | 9 | 추가 조건 B를 만족하고, 이다. |
| 8 | 16 | 추가 조건 B를 만족한다. |
| 9 | 9 | . |
| 10 | 13 | . |
| 11 | 18 | 추가적인 제약이 없다. |
各サブタスクの得点は、そのサブタスクに属するテストケースの得点の最小値である。