AT_rcl_contest_2021_long_a 農場王X
题目描述
农场起初没有任何蔬菜，但已知将有 $ M $ 颗蔬菜会逐渐生长。每颗蔬菜的信息用 $ R_i, C_i, S_i, E_i, V_i $ 表示，表示这颗蔬菜将在第 $ S_i $ 天从位置 $ (R_i, C_i) $ 长出，存活至第 $ E_i $ 天结束，价值为 $ V_i $。
X 可以购买和使用收割机来收割蔬菜。初始状态没有收割机，但有 $ 1 $ 单位资金。从第 $ 0 $ 天开始直到第 $ T-1 $ 天，每天 X 可以选择以下操作之一：
- **购买收割机**：X 可以购买一台新收割机并将其放置在一个没有收割机的格子上。若已经拥有 $ j $ 台收割机，则购买第 $ j+1 $ 台需要 $ (j+1)^3 $ 单位资金。
- **移动收割机**：可以选择移动一个已放置的收割机到一个新的无收割机的格子。
- **无操作**：选择什么都不做。
每天操作结束后，会进行以下处理：
- 如果有蔬菜在当天出现（$ S_i = t $），则这些蔬菜在其指定的区划中生长。
- 若一个区划内同时有蔬菜和收割机，则进行收割。具体来说，蔬菜的价值为 $ v $，而能从这个区划通过上下左右移动到达的带有收割机的区划数为 $ k $，则会获得 $ v \times k $ 的收益。
- 当天结束时，所有存在 $ E_i = t $ 的蔬菜会枯萎。
请合理安排 X 的操作，使得在第 $ T-1 $ 天结束时，X 拥有的资金尽可能多。
### 分数计算
以第 $ T-1 $ 天结束时 X 所拥有的资金作为得分。各个测试用例的得分总和即为最终提交的得分。
- **暂定测试**：包含 50 个测试用例。只要有一个测试用例未通过，提交得分即为 0 分。
- **系统测试**：包含 1000 个测试用例。仅未通过的测试用例得 0 分。请注意，因执行时间可能有浮动，务必计时或者在程序设计上预留时间余量。
输入格式
输入为以下格式：
第一行包含三个整数 $ N, M, T $。接下来的 $ M $ 行，每行包含五个整数。
```
N M T
R_0 C_0 S_0 E_0 V_0
...
R_{M-1} C_{M-1} S_{M-1} E_{M-1} V_{M-1}
```
- $ N $ 为农场的大小，固定为 $ 16 $。
- $ M $ 为蔬菜的数量，固定为 $ 5000 $。
- $ T $ 为操作的天数，固定为 $ 1000 $。
- $ R_i, C_i $ 表示第 $ i $ 颗蔬菜出现的区划，合法范围为 $ 0 \leq R_i, C_i < N $。
- $ S_i, E_i $ 分别为蔬菜出现和枯萎的具体日子，$ 0 \leq S_i \leq E_i < T $。
输出格式
输出 $ T $ 行，每行表示当天的操作：
- **购买收割机**：输出两个整数 $ r_1, c_1 $，表示将收割机放置在 $ (r_1, c_1) $。
- **移动收割机**：输出四个整数 $ r_1, c_1, r_2, c_2 $，表示移动收割机从 $ (r_1, c_1) $ 到 $ (r_2, c_2) $。
- 可以移动到原位置，即 $ r_1, c_1, r_2, c_2 $ 可以相等。
- **无操作**：输出 -1。
请根据以上规则设计输出，确保最大化 X 的资金。
**本翻译由 AI 自动生成**
说明/提示
### テストケースの生成について
それぞれの野菜は次のように生成します。
厳密にはテストケースジェネレータの実装を見てください。
- $ i $ 番目の野菜が生えている日数を表す整数 $ l_{i} $ を $ 0 $ 以上 $ 20 $ 以下の整数から一様ランダムに選択します。
- $ S_{i} $ を $ 0 $ 以上 $ T-1-l_{i} $ 以下の整数から一様ランダムに選択します。
- $ E_{i}\ =\ S_{i}\ +\ l_{i} $ とします。
- $ v_{i} $ を $ 0 $ 以上 $ 1.0+S_{i}/100.0 $ 以下の浮動小数点数から一様ランダムに選択します。
- $ V_{i}\ =\ \text{floor}(2^{v_{i}}) $ とします。 $ \text{floor}(x) $ は $ x $ を超えない最大の整数を表します。
- $ R_{i},C_{i} $は $ 0 $ 以上 $ N $ 未満の整数から一様ランダムに選択します。
- 生成済みの野菜のどれかと同じ区画で存在期間が重なる場合は、この野菜について始めからやり直します。
生成された野菜たちを $ (S_{i},R_{i},C_{i}) $ の辞書順にソートします。
### 配布物について
テストケースジェネレータ・テスター・サンプル入力データ・ビジュアライザ・サンプルコードを次のリンクから提供しています。
[テスター類 (zip)](https://img.atcoder.jp/rcl-contest-2021-long/9ee3ca1da522fff7e369dd7f470f1e7a.zip)
### ビジュアライザの説明
入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。
- このビジュアライザはデスクトップ版の [Google Chrome](https://www.google.co.jp/chrome/) および [Mozilla Firefox](https://www.mozilla.org/firefox/new/) の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
- このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
- このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。
ビジュアライザは配布物にも含まれ、使用方法については配布物内のREADME\_ja.htmlに書いてあります。
### Sample Explanation 1
注意: この入力は説明用のもので、テストケースとしての制約を満たしていません。 入出力例の説明をします。 プログラムの出力 説明 収穫機の区画 資金の変化 ```
```
3 3 ``` $ 0 $ 日目は資金 $ 1 $ を用いて収穫機を購入し、 $ (3,3) $ に配置します。 ```--------- --------- --------- ---o----- --------- --------- --------- --------- --------- ``` ```1 -> 0 ``` ```-1 ``` $ 1 $ 日目はパスをします。 その後の処理で $ (3,3) $ に野菜が生えるのでこれを収穫し、資金 $ 35 $ を得ます。 ```--------- --------- --------- ---o----- --------- --------- --------- --------- --------- ``` ```0 -> 35 ``` ```2 3 ``` $ 2 $ 日目は資金 $ 8 $ を用いて収穫機を購入し、 $ (2,3) $ に配置します。 ```--------- --------- ---o----- ---o----- --------- --------- --------- --------- --------- ``` ```35 -> 27 ``` ```3 4 ``` $ 3 $ 日目は資金 $ 27 $ を用いて収穫機を購入し、 $ (3,4) $ に配置します。 ```--------- --------- ---o----- ---oo---- --------- --------- --------- --------- --------- ``` ```27 -> 0 ``` ```2 3 4 4 ``` $ 4 $ 日目は $ (2,3) $ に配置してある収穫機を $ (4,4) $ に移動します。 その後の処理で $ (4,4) $ に野菜が生えるのでこれを収穫し、資金 $ 22\ \times\ 3\ =\ 66 $ を得ます。 ```--------- --------- --------- ---oo---- ----o---- --------- --------- --------- --------- ``` ```0 -> 66 ``` ```3 3 7 8 ``` $ 5 $ 日目は $ (3,3) $ に配置してある収穫機を $ (7,8) $ に移動します。 ```--------- --------- --------- ----o---- ----o---- --------- --------- --------o --------- ``` ```66 -> 66 ``` ```4 4 7 7 ``` $ 6 $ 日目は $ (4,4) $ に配置してある収穫機を $ (7,7) $ に移動します。 ```--------- --------- --------- ----o---- --------- --------- --------- -------oo --------- ``` ```66 -> 66 ``` ```3 4 8 7 ``` $ 7 $ 日目は $ (3,4) $ に配置してある収穫機を $ (8,7) $ に移動します。 ```--------- --------- --------- --------- --------- --------- --------- -------oo -------o- ``` ```66 -> 66 ``` ```8 8 ``` $ 8 $ 日目は資金 $ 64 $ を用いて収穫機を購入し、 $ (8,8) $ に配置します。 その後の処理で $ (8,8) $ に生えている野菜を収穫し、資金 $ 20\ \times\ 4\ =\ 80 $ を得ます。 ```--------- --------- --------- --------- --------- --------- --------- -------oo -------oo ``` ```66 -> 82 ``` ```-1 ``` $ 9 $ 日目はパスをします。 その後の処理で $ (2,3) $ の野菜は消滅します。 ```--------- --------- --------- --------- --------- --------- --------- -------oo -------oo ``` ```82 -> 82 ``` この出力例で得られる得点は $ 82 $ 点となります。 ```