AT_rcl_contest_2021_long_a 農場王X
Description
[problemUrl]: https://atcoder.jp/contests/rcl-contest-2021-long/tasks/rcl_contest_2021_long_a
Xは農場を所有しており、その農場は $ N $ 行 $ N $ 列のマス目で表されます。
上から $ r $ 行目、左から $ c $ 列目のマスを区画 $ (r,\ c) $ で表します。 $ (0\
Input Format
入力は以下の形式で標準入力から与えられます。
1行目にはスペース区切りで整数 $ N,M,T $ を含みます。続く $ M $ 行のそれぞれには、スペース区切りで整数を $ 5 $ 個含みます。
> $ N $ $ M $ $ T $ $ R_{0} $ $ C_{0} $ $ S_{0} $ $ E_{0} $ $ V_{0} $ \\(\\vdots\\) $ R_{i} $ $ C_{i} $ $ S_{i} $ $ E_{i} $ $ V_{i} $ \\(\\vdots\\) $ R_{M-1} $ $ C_{M-1} $ $ S_{M-1} $ $ E_{M-1} $ $ V_{M-1} $
- $ N $ は農場のサイズを表す整数で、 $ N=16 $ を満たします。
- $ M $ は発生する野菜の個数を表す整数で、 $ M=5000 $ を満たします。
- $ T $ は行動を行える日数の期間を表す整数で、 $ T=1000 $ を満たします。
- $ R_{i} $ および $ C_{i} $ は $ i $ 番目の野菜が生える区画 $ (R_{i},C_{i}) $ を表す整数で、$ 0\
Output Format
$ T $行出力してください。
$ i $行目に $ i $ 回目の行動を出力します。
- 購入を行う場合は、整数を $ 2 $ つ、スペース区切りで出力してください。
- 購入した収穫機を $ (r_{1},c_{1}) $ に置く場合 $ r_{1} c_{1} $ と出力してください。
- 移動を行う場合は、整数を $ 4 $ つ、スペース区切りで出力してください。
- $ (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 $ のみを出力してください。
Explanation/Hint
### テストケースの生成について
それぞれの野菜は次のように生成します。
厳密にはテストケースジェネレータの実装を見てください。
- $ 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 $ 点となります。 ```