AT_ahc058_a [AHC058A] Apple Incremental Game

APPLE ARTIS社（通称 AA社）は、りんごの大量生産を生業とする企業である。このたび、長年の研究の成果により、無からりんごを生み出す革新的な機械の開発に成功した。 しかし、この機械を用いてりんごを本格的に大量生産するには、機械そのものを大量に生産する必要がある。そこでAA社は、りんご生産機を生産するための機械生産機、さらにその機械生産機を生産するための機械生産機生産機、というように階層的に機械を生み出す仕組みを構築した。 AA社のエンジニアであるあなたは、これらの階層的な機械群を活用し、できるだけ多くのりんごを生産するための生産計画アルゴリズムを構築する任務を任された。

$ N $ 種類のIDと $ L $ 種類のLevelからなる $ N \times L $ 種類の機械が存在し、Levelが $ i $ 、IDが $ j $ の機械を**機械 $ j^i $** と呼ぶ（ $ 0 \leq i < L,\ 0 \leq j < N $ ）。 機械 $ j^0 $ の生産能力は $ A_j $ である。また、機械 $ j^i $ の初期コストは $ C_{i,j} $ である。 以下の生産計画の手順に従い、全 $ T $ ターン終了時点でのりんごの総数を最大化することが目的である。 #### 生産計画の手順 機械 $ j^i $ の個数を $ B_{i,j} $ とし、計画開始時点ではすべて $ 1 $ である。 また、機械 $ j^i $ のパワーを $ P_{i,j} $ とし、開始時点ではすべて $ 0 $ である。 計画開始時点でのりんごの数は $ K $ である。 各ターンは以下の手順で進行する。 1. あなたは以下の2つの行動のうちいずれか1つを選択する。 - 機械 $ j^i $ を強化する：りんごを $ C_{i,j} \times (P_{i,j} + 1) $ 消費し、 $ P_{i,j} $ を1増やす。ただし、りんごの数が負になるような強化は行えない。 - 何もしない。 2. Level 0, 1, 2, 3 の順に、すべての機械 $ j^i $ について以下の処理を行う。 - Level 0 の機械（ $ i = 0 $ ）の場合： - りんごを $ A_j \times B_{i,j} \times P_{i,j} $ 増加させる。 - Level 1 以上の機械（ $ i \geq 1 $ ）の場合： - $ B_{i-1,j} $ を $ B_{i,j} \times P_{i,j} $ 増加させる。 上手に行動を選択し、 $ T $ ターン終了時点でのりんごの数をできるだけ多くしてほしい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ L $ $ T $ $ K $ $ A_0 $ $ A_1 $ $ \cdots $ $ A_{N-1} $ $ C_{0,0} $ $ C_{0,1} $ $ \cdots $ $ C_{0,N-1} $ $ C_{1,0} $ $ C_{1,1} $ $ \cdots $ $ C_{1,N-1} $ $ \vdots $ $ C_{L-1,0} $ $ C_{L-1,1} $ $ \cdots $ $ C_{L-1,N-1} $ - 1行目には、4つの整数 $ N, L, T, K $ が与えられる。 - $ N $ は機械のIDの種類数であり、 $ N = 10 $ を満たす。 - $ L $ は機械のLevelの種類数であり、 $ L = 4 $ を満たす。 - $ T $ は総ターン数であり、 $ T = 500 $ を満たす。 - $ K $ は計画開始時点のりんごの数であり、 $ K = 1 $ を満たす。 - 2行目には、Level 0 の機械の生産能力を表す $ N $ 個の整数 $ A_0, A_1, \dots, A_{N-1} $ が空白区切りで与えられる。 - $ A_j $ は機械 $ j^0 $ の生産能力であり、 $ 1 \leq A_j \leq 100 $ を満たす。 - $ A $ は昇順にソートされている（ $ A_0 \leq A_1 \leq \cdots \leq A_{N-1} $ ）。 - 続く $ L $ 行には、それぞれ $ N $ 個の整数 $ C_{i,j} $ が空白区切りで与えられる。 - $ C_{i,j} $ は機械 $ j^i $ の初期コストであり、 $ 1 \leq C_{i,j} \leq 1.25 \times 10^{12} $ を満たす。

ちょうど $ T $ 行出力せよ。 各行には、 $ t $ ターン目（ $ 0 \leq t < T $ ）に行う行動を、 $ 0 $ ターン目から順に以下の形式で出力すること。 - 機械 $ j^i $ を強化する場合 > $ i $ $ j $ - 何もしない場合 ``` -1 ``` 解答プログラムは、`#` から始まるコメント行を出力に含めても良い。 [例を見る](https://img.atcoder.jp/ahc058/UpvAVdx6.html?lang=ja&seed=0&output=sample)

### 得点 $ T $ ターン後の時点におけるりんごの数を $ S $ としたとき、 $ \mathrm{round}(10^5 \times \log_2 S) $ の得点が得られる。 得点は大きいほど良い。 以下の場合、WAとなる。 - りんごの数が $ 0 $ 未満になるような強化を行った場合 - 存在しない機械のLevelまたはIDを指定した場合 - 行動回数が $ T $ 未満の場合 合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ L $ 以上 $ U $ 以下の実数値を一様ランダムに生成する関数を $ \mathrm{rand\_double}(L,U) $ で表す。 #### $ A_j $ の生成 - $ j=0 $ のとき： $ A_0=1 $ - $ j \neq 0 $ のとき： $ A_j=\mathrm{round}(10^{\mathrm{rand\_double}(0,2)}) $ - 生成後、 $ A $ 配列を昇順にソートする #### $ C_{i,j} $ の生成 - $ i=0 $ かつ $ j=0 $ のとき： $ C_{0,0}=1 $ - それ以外のとき： $ C_{i,j}=\mathrm{round}(A_j \times 500^i \times 10^{\mathrm{rand\_double}(0,2)}) $ ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/ahc058/UpvAVdx6.html?lang=ja): ローカル版より高性能でアニメーション表示と手動プレイが可能です。 - [ローカル版](https://img.atcoder.jp/ahc058/UpvAVdx6.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/ahc058/UpvAVdx6_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。