AT_ahc055_a [AHC055A] Weakpoint

Nihonbashi Treasure Island は架空の国Rで大人気の小説であり、あなたはこの小説をベースにしたゲームの大ファンである。 このゲームでは、たくさんの宝箱が出現する。宝箱を開くと武器が入手でき、武器を用いてゲームを有利に進めることができる。 宝箱を開くには、素手または武器を用いて宝箱を攻撃する必要がある。ゲーム内のすべての宝箱を開けると隠しエンディングが開放されるという話を聞いたあなたは、いち早くエンディングを見るべく、少ない攻撃回数ですべての宝箱を開く方法を探すことにした。 ### 問題文 $ N $ 個の宝箱があり、 $ i $ 番目の宝箱を宝箱 $ i $ と呼ぶ $ (0 \le i \lt N) $ 。宝箱 $ i $ の初期の硬さは $ H_i $ である。また、宝箱 $ i $ の中には武器 $ i $ が入っている。 宝箱 $ i $ の硬さを $ 0 $ 以下にすると宝箱 $ i $ が開き、武器 $ i $ が利用可能になる。武器には耐久値が存在し、武器 $ i $ の耐久値は $ C_i $ である。 素手または利用可能な武器を用いて、宝箱を攻撃することができる。 - 素手で攻撃: 素手で宝箱 $ b $ に攻撃したとき、宝箱 $ b $ の硬さを $ 1 $ 減らす。素手での攻撃回数に制限はない。 - 武器で攻撃: 武器 $ w $ で宝箱 $ b $ に攻撃したとき、宝箱 $ b $ の硬さを $ A_{w,b} $ 減らし、武器 $ w $ の耐久値が $ 1 $ 減る。武器 $ w $ の耐久値が $ 0 $ になったとき、武器 $ w $ は壊れて攻撃に用いることができなくなる。 できるだけ少ない回数ですべての宝箱を開ける攻撃手順を求めよ。

N/A

入力は以下の形式で標準入力から与えられる。 ``` \( N \\ H_0 ~ H_1 ~ \ldots ~ H_{N-1} \\ C_0 ~ C_1 ~ \ldots ~ C_{N-1} \\ A_{0,0} ~ A_{0,1} ~ \ldots ~ A_{0,N-1} \\ A_{1,0} ~ A_{1,1} ~ \ldots ~ A_{1,N-1} \\ \vdots \\ A_{N-1,0} ~ A_{N-1,1} ~ \ldots ~ A_{N-1,N-1} \) ``` - 1行目には1つの整数 $ N $ が与えられる。 $ N $ は宝箱の数で、 $ N = 200 $ を満たす。 - 2行目には、宝箱の初期の硬さを表す $ N $ 個の整数 $ H_0, H_1, \ldots, H_{N-1} $ が空白区切りで与えられる。宝箱 $ i $ の硬さは $ H_i $ であり、 $ 100 \leq H_i \leq 500 $ を満たす。 - 3行目には、武器の耐久値を表す $ N $ 個の整数 $ C_0, C_1, \ldots, C_{N-1} $ が空白区切りで与えられる。武器 $ i $ の耐久値は $ C_i $ であり、 $ 1 \leq C_i \leq 6 $ を満たす。 - 続く $ N $ 行には、各行について $ N $ 個の整数 $ A_{i, j} $ が空白区切りで与えられる。 - $ A_{i,j} $ は、武器 $ i $ で宝箱 $ j $ を攻撃したときに宝箱 $ j $ の硬さを減らす値であり、 $ 1 \leq A_{i,j} \leq 500 $ を満たす。 ### 出力 宝箱を攻撃した回数を $ T $ とする。 $ T $ 行出力せよ。 ``` \( W_{0}~B_{0}\\ \vdots \\ W_{T-1} ~ B_{T-1} \) ``` 各行には、 $ i $ 回目の攻撃で用いた武器の番号 $ W_i $ と攻撃対象の宝箱の番号 $ B_i $ をこの順に空白区切りで出力せよ。なお、 $ i $ 回目の攻撃が素手で行われた場合は、 $ W_i $ は `-1` として出力せよ。 [例を見る](https://img.atcoder.jp/ahc055/ys4u9l6aru.html?lang=ja&output=sample)

N/A

### 得点 すべての宝箱を開けるために攻撃した回数が $ T $ のとき、\\( \\sum\_{i=0}^{N-1} H\_i - T + 1 \\) の得点が得られる。 以下に挙げる不正な出力をした場合、WAと判定される。 - すでに開いた宝箱を攻撃する - 利用可能になっていない武器を使用して攻撃する - 耐久値が $ 0 $ になった武器を使用して攻撃する - 存在しない武器の番号や宝箱の番号を出力する - すべての攻撃を終えた状態で開いていない宝箱がある 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ L $ 以上 $ U $ 以下の整数を一様ランダムに生成する関数を $ \mathrm{rand}(L, U) $ 、 $ L $ 以上 $ U $ 以下の実数を一様ランダムに生成する関数を $ \mathrm{rand\_double}(L, U) $ とする。 $ H_i $ , $ C_i $ , $ A_{i,j} $ $ (0 \le i \lt N, 0 \le j \lt N) $ をそれぞれ独立に、以下のようにして生成する。 - $ H_i = \mathrm{rand}(100, 500) $ - $ C_i = \mathrm{rand}(1, 6) $ - $ A_{i,j} = \mathrm{round}(500.0 / \mathrm{rand\_double}(1.0, 500.0)) $ ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc055/ys4u9l6aru.html): ローカル版より高機能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/ahc055/ys4u9l6aru.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc055/ys4u9l6aru_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。