A - Farm King X

Contest Duration: 2021-09-05 18:00:00+0900 - 2021-09-12 18:00:00+0900 (local time) Back to Home

A - Farm King X Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

Xは農場を所有しており、その農場は N 行 N 列のマス目で表されます。
上から r 行目、左から c 列目のマスを区画 (r, c) で表します。 (0≤r, c＜N)
はじめ、農場のどの区画にも野菜はありません。
いずれかの区画に M 個の野菜が生えることがわかっています。

i 番目の野菜は R_{i},C_{i},S_{i},E_{i},V_{i} で表されます。
これは S_{i} 日目に区画 (R_{i},C_{i}) に価値 V_{i} の野菜が生え、E_{i} 日目の終わりに枯れるということを表します。

Xは収穫機を使って野菜を収穫していきます。
初期状態では収穫機は持っておらず、資金を 1 持っています。

0 日目から T-1 日目の毎日、Xは以下のいずれかの行動をします。

収穫機の購入

新たな収穫機を 1 台購入し、収穫機が存在しない区画のうちひとつを選んでそこへ配置します。
収穫機を j 個所持している時の購入には資金が (j+1)^3 かかります。
すなわち、初回の購入には資金 1 が、その次の購入には資金 8 が、さらにその次には資金 27 が必要です。
資金が足りない場合には購入できません。

収穫機の移動
- すでに配置されている収穫機を 1 台選び、収穫機が存在しない別の区画に移動させます。
パス
- なにもしません。

t(0≤t＜T) 回目の行動を取った後、以下の処理が行われます。

S_{i}=t の野菜について、区画 (R_{i},C_{i}) にその野菜が出現します。
野菜と収穫機の両方が存在する区画について、野菜の収穫を行います。具体的には、その野菜の価値を v、その区画から収穫機がある区画だけを上下左右に辿って到達できる区画の数を k として、資金を v \times k 得た後、その野菜が消滅します。
農場内に存在する野菜のうち、E_{i}=t の野菜が消滅します。

Xの行動をうまく決めることで、 T-1 日目終了時で、できるだけ多くの資金をXが持っているようにしてください。

スコア

T-1 日目終了時にXが所持している資金が得点となります。
各テストケースの得点の合計が提出の得点となります。

暫定テストは 50 個のテストケースを用います。 1 つ以上のテストケースで AC 以外の判定がされた場合、提出の得点は 0 点となります。
システムテストは 1000 個のテストケースを用います。AC 以外の判定がされた場合、そのテストケースのみ 0 点となります。
実行時間には多少のブレが生じるため、実行時間制限ギリギリの提出がシステムテストで TLE となる可能性があります。プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。
コンテスト終了後に、seeds.txt(md5=75031719692fe939fb105e7af16e31c8)を公開します。

入力

入力は以下の形式で標準入力から与えられます。
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≤R_{i}＜N, 0≤C_{i}＜N を満たします。
S_{i} は i 番目の野菜が出現する日を表す整数で、 S_{i}≤S_{i+1},0≤S_{i}＜T を満たします。
E_{i} は i 番目の野菜が消滅する日を表す整数で、 S_{i}≤E_{i}＜T を満たします。
V_{i} は i 番目の野菜の価値を表す整数で、取り得る値の範囲については下記の「テストケースの生成について」を参照ください。
(R_i, C_i)=(R_j, C_j) となる i,j (i＜j) が存在するならば E_i＜S_j であることが保証されます。すなわち、同じ区画の野菜の存在期間は重なりません。

出力

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 のみを出力してください。

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

それぞれの野菜は次のように生成します。
厳密にはテストケースジェネレータの実装を見てください。

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}) の辞書順にソートします。

入力例

注意: この入力は説明用のもので、テストケースとしての制約を満たしていません。

出力例

入出力例の説明をします。

プログラムの出力	説明	収穫機の区画	資金の変化
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 点となります。

配布物について

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

テスター類 (zip)

ビジュアライザの説明

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

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

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

Problem Statement

Mr.X has a large farm, which consists of N \times N squares.
We call the square at the r-th row from the top and at the c-th column from the left as the area (r, c) (0≤r, c＜N).

M vegetables will grow and die on the farm in the coming T days.
The i-th vegetable is represented by five integers R_{i},C_{i},S_{i},E_{i}, and V_{i}.
They mean that a vegetable with the value V_{i} will appear in the area (R_{i},C_{i}) on the S_{i}-th day, and disappear at the end of the E_{i}-th day.

X harvests these vegetables with harvest machines.
At first, he doesn't have any harvest machines and has 1 unit of money.

On each of the T days, X makes one of the following actions.

Purchase

X gets a new harvest machine and puts it in one of the areas that doesn't have another harvest machine.
When X has j harvest machines, purchase costs (j+1)^3 units of money.
- For example, the first purchase costs 1 unit of money. The second purchase costs 8 units of money, and so on.
X can't purchase a machine if he doesn't have enough money.

Move
- X chooses a harvest machine and moves it to one of the areas where no harvest machine is located.
Pass
- X does nothing.

After the t-th (0≤t＜T) action, the following things happen in order.

For all i where S_{i} = t, vegetable i appears in the area (R_{i},C_{i}).
Vegetables in the areas that have a harvest machine are harvested.
- For each of such vegetables, let v be its value, and k be the size of the 4-connected component of the areas having a harvest machine that contains the vegetable's position.
  - 4-connected component is the group of areas that are connected to each other through vertically or horizontally adjacent areas.
- X earns v \times k units of money.
- This vegetable disappears.
For all i where E_{i} = t, vegetable i disappears from the farm if it's not yet harvested.

Your goal is to make as much money as possible he has after the T-1-th day by determining actions X will take.

Scoring

The score of a test case is the amount of money X has after the T-1-th day.
The score of a submission is the total score for each test case.

Provisional tests consist of 50 test cases. If you get a result other than AC for one or more test cases, the score of the submission will be zero.
System tests consist of 1000 test cases. If you get a result other than AC for some test cases, only the score for those test cases will be zero.
Since there will be some variance in the execution time, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time. We will publish seeds.txt (md5=75031719692fe939fb105e7af16e31c8) after the contest is over.

Input

Input is given from standard input in the following format.
The first line consists of the three integers N,M,T separated by a space. Each of the next M lines consists of the five integers separated by a space.

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 is an integer that represents the size of the farm and satisfies N=16.
M is an integer that represents the number of the vegetables and satisfies M=5000.
T is an integer that represents the number of days and satisfies T=1000.
R_{i} and C_{i} are integers that represent the area in which i-th vegetable appears, and satisfy 0≤R_{i}＜N, 0≤C_{i}＜N.
S_{i} is an integer that represents the day which i-th vegetable appears on, and satisfies S_{i}≤S_{i+1},0≤S_{i}＜T.
E_{i} is an integer that represents the day which i-th vegetable disappears on, and satisfies S_{i}≤E_{i}＜T.
V_{i} is an integer that represents the value of the i-th vegetable. See the "test case generation" section below about the details.
If (R_i, C_i)=(R_j, C_j) (i＜j) , then E_i＜S_j. That is, the lifetimes of the vegetables that appear in the same area don't overlap.

Output

Output Tlines.
i-th line represents X's i-th action.

For making a purchase, output two integers separated by a space.

To put the purchased harvest machine in the area (r_{1},c_{1}), output r_{1} c_{1}.

For doing a move, output two integers separated by a space.

To move a harvest machine from the area (r_{1},c_{1}) to the area (r_{2},c_{2}), output r_{1} c_{1} r_{2} c_{2}.
(r_{1},c_{1}) may be the same as (r_{2},c_{2}).

For doing pass, output -1.

Test case generaton

Each vegetable is generated as follows.
All random selection is uniformly at random.
For the exact details, see the source code of the test case generator.

l_{i} is selected from the integers between 0 and 20, inclusive.
S_{i} is selected from the integers between 0 and T-1-l_{i}, inclusive.
E_{i} is S_{i} + l_{i}.
v_{i} is selected from the floating point numbers greater than or equal to 0.0 and less than or equal to 1.0+S_{i}/100.0.
V_{i} is \text{floor}(2^{v_{i}}).
- \text{floor}(x) means the largest integer not greater than x.
R_{i} and C_{i} are selected independently from the integers between 0 and N-1, inclusive.
If any of the already generated vegetables has the same (R_{i},C_{i}) as the newly generated one and its lifetime overlaps with the newly generated one, the generation is executed again on this vegetable.

Generated M vegetables are sorted lexicographically by the tuples (S_{i},R_{i},C_{i}).

Sample Input

Notice: This input is for the explanation purpose and doesn't conform to the constraint.

Sample Output

Output	Explanation	Harvest Machines Placement	Change of Money
3 3	X purchases a harvest machine with `1` unit of money, and places it to the area `(3,3)`.	--------- --------- --------- ---o----- --------- --------- --------- --------- ---------	1 -> 0
-1	X does nothing. A vegetable appears in the area `(3,3)` and is harvested. X earns `35 \times 1 = 35` units of money.	--------- --------- --------- ---o----- --------- --------- --------- --------- ---------	0 -> 35
2 3	X purchases a harvest machine with `8` units of money, and places it to the area `(2,3)`.	--------- --------- ---o----- ---o----- --------- --------- --------- --------- ---------	35 -> 27
3 4	X purchases a harvest machine with `27` units of money, and places it to the area `(3,4)`.	--------- --------- ---o----- ---oo---- --------- --------- --------- --------- ---------	27 -> 0
2 3 4 4	X moves a harvest machine located on `(2,3)` to the area `(4,4)`. After that, a vegetable appears in the area `(4,4)` and is harvested. X earns `22 \times 3 = 66` units of money.	--------- --------- --------- ---oo---- ----o---- --------- --------- --------- ---------	0 -> 66
3 3 7 8	X moves a harvest machine located on `(3,3)` to the area `(7,8)`.	--------- --------- --------- ----o---- ----o---- --------- --------- --------o ---------	66 -> 66
4 4 7 7	X moves a harvest machine located on `(4,4)` to the area `(7,7)`.	--------- --------- --------- ----o---- --------- --------- --------- -------oo ---------	66 -> 66
3 4 8 7	X moves a harvest machine located on `(3,4)` to the area `(8,7)`.	--------- --------- --------- --------- --------- --------- --------- -------oo -------o-	66 -> 66
8 8	X purchases a harvest machine with `64` units of money, and places it to the area `(8,8)`. After that, a vegetable in the area `(8,8)` is harvested. X earns `20 \times 4 = 80` units of money.	--------- --------- --------- --------- --------- --------- --------- -------oo -------oo	66 -> 82
-1	X does nothing. A vegetable in the area `(2,3)` disappears.	--------- --------- --------- --------- --------- --------- --------- -------oo -------oo	82 -> 82

The score obtained from this output is 82.

Tools

We provide the tools for contestants. It contains test case generator, output verifier, sample input data, solution visualizer, and sample solutions (C++, Python).

contestant tools(zip)

Visualizer

This visualizer is tested on the latest desktop version of Google Chrome and Mozilla Firefox. We don't guarantee that it works on every browser.
The score calculated on this visualizer is not the actual score of the contest. Submit your solution on the AtCoder contest page to enter the contest.
Use this visualizer at your own risk.

This visualizer is also contained in the contestant tools.

input file

output file

fps

save as image

money

action

machines

price

log