A - 魔法使いXの戦い Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

魔法使いXはいまモンスターの大群と対峙しています。モンスターは N 匹いて、横一列に並んでいます。
モンスターにはそれぞれ強さがあり、左から i 番目のモンスターの強さを A_i と表します。

魔法使いXが使える魔法は唯一つ、「パワーアップ」です。
「パワーアップ」はモンスター1匹の強さを、もう1匹のモンスターの強さ分だけ上げるという魔法です。
具体的には以下のような手順を経ます。

  1. 強さを変化させたいモンスターを1匹選ぶ。このモンスターの左からの位置を p とする。
  2. モンスターをさらに1匹選ぶ。このモンスターの左からの位置を q とする。このとき p = q でもよい。
  3. p 番目のモンスターの強さが、\(A_{p} = (A_{p} + A_{q}) \% K\) へと変化する。ここで、\% K は K で割った余りを表す。
    （K はこの世界における強さの制限値で、強さが K 以上になった場合はオーバーフローしてしまいます）

また、魔法使いXは「パワーアップ」を最大 M 回まで唱えることができます。

「パワーアップ」をかけるモンスターをうまく選び、 魔法を唱え終わった後のそれぞれのモンスターの強さをできるだけ小さい値にして、戦いを有利にしてください。

各テストケースの得点およびこの問題の得点は、次のように計算されます。

  • 1つのテストケースでは、以下の式でスコアが計算されます。 \[score = \text{ceil}\left(\sum_{i}(\log_{2}K - \log_{2}(A_{i} + 1))\right)\] なお、\text{ceil}(x) は x 以上の最小の整数を表します。
    また、魔法を唱え終わった後の A で 0 でない値が1個以下の場合、M - (魔法を唱えた回数) をスコアに加えます。
  • テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。

入力

入力は以下の形式で標準入力から与えられます。
1行目には整数 N, M, K がスペース区切りで与えられます。2行目には N 個の整数がスペース区切りで与えられます。 

\(\begin{array}{lll}
    N & M & K\\
    A_{ 0 } & \ldots & A_{ N-1 }
  \end{array}\)
  • N はモンスターの数で、N = 300 を満たします。
  • M はXが唱えられる魔法の回数で、M = 1000 を満たします。
  • K は強さの制限値で、K = 10^8 を満たします。
  • A_{i} は左から i 番目のモンスターの強さを表す整数で、0 < A_{i} < K を満たします。

出力

出力は M 行以下で、各行にはスペース区切りで 2 個の整数を標準出力へ出力してください。

\(\begin{array}{lll}
    p_{0} &  q_{0} \\
    \vdots &  \vdots \\
  \end{array}\)
  • p_{i} は i 回目の「パワーアップ」の手順1で選んだモンスターの位置で、0 ≤ p_i ≤ N - 1 を満たす必要があります。
  • q_{i} は i 回目の「パワーアップ」の手順2で選んだモンスターの位置で、0 ≤ q_i ≤ N - 1 を満たす必要があります。
  • p_{i} = q_i でもよいです。
  • 出力が上記の制約を満たさない場合、 となります。

テストケースの生成について

各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータはページ下部のリンクより提供しています。
各 A_{i} の値は、1 以上 K 未満の整数から一様ランダムに独立に選ばれます。

入力例1

5 10 100
75 99 51 48 1
このケースは説明用のもので、入力の制約（ N = 300, M = 1000, K = 10^8）を満たしていません。

出力例1

0 0
0 0
3 4
3 2
2 1
2 2
1 4
各「パワーアップ」後の A は以下のようになります。 
50 99 51 48 1
0 99 51 48 1
0 99 51 49 1
0 99 51 0 1
0 99 50 0 1
0 99 0 0 1
0 0 0 0 1
このケースでは、スコアの計算式は \( \text{ceil}(4(\log_2(100) - \log_2(0+1)) + (\log_2(100) - \log_2(1+1))) \fallingdotseq \text{ceil}(32.21\cdots) = 33\)となります。
また、魔法を唱え終わった後の A で 0 でない値が1個以下なので、10 - 7 = 3 がスコアに加算され、
最終的には、33 + 3 = 36 がスコアとなります。

配布物について

テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザを次のリンクから提供しています。

テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザ (zip)

ビジュアライザの説明

入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。

  • このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
  • このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
  • このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

ビジュアライザは配布物にも含まれ、使用方法については配布物内のREADME.htmlに書いてあります。

input file
output file
fps
command
A_p difference
score
save as image