Time Limit: 5 sec / Memory Limit: 1024 MB
問題文
N 行 N 列のグリッドで表される土地があります。
グリッドのうち W 箇所に水源があり、 K 箇所に家があります。
土地の上から i 行目（ 0 \leq i \lt N ）、左から j 列目（ 0 \leq j \lt N ）のセルを (i, j) と表すことにします。
各セル (i, j) の岩盤には、10 以上 5000 以下の整数で表される 頑丈さ S_{i,j} が予め設定されていますが、これらの値は入力では与えられません。
水源が存在するセルの岩盤を破壊すると、そのセルに水が流れます。
また、水が流れているセルの上下左右に隣接する岩盤が破壊されたセルにも水が流れます。
土地の管理者であるXさんは、いくつかの岩盤を破壊して、家が存在する全てのセルに水が流れるようにしたいです。
家が存在するセルに水を流すには、そのセルの岩盤も破壊する必要がある点に注意してください。
岩盤を破壊するためには、Xさんは以下の掘削を繰り返し行います。
- まだ岩盤が破壊されていないセル (i, j) を一つと、パワーを表す 5000 以下の正の整数 P を一つ選びます。
- Xさんの体力を C+P （C は入力で与えられる正の整数）消費して、セルの岩盤の頑丈さ S_{i,j} を P 減らします。
- この操作で S_{i,j} \leq 0 となった場合、セル (i, j) の岩盤が破壊されます。
なるべくXさんの体力を消費しないように工夫しながら、家が存在する全てのセルに水が流れるようにしてください。
得点・順位付け
相対評価システムを採用します。
各テストケース毎に、\mathrm{round} \lparen 10^9 \times \frac{全参加者中の最小消費体力}{自身の消費体力} \rparen の相対評価スコアが得られ、その和が提出の得点となります。
最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定されます。暫定テスト・システムテストのどちらにおいても、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースに関する相対評価スコアは0点となり、そのテストケースにおいては「全参加者中の最小消費体力」の計算対象から除外されます。
また、システムテストは CE 以外の結果を得た一番最後の提出に対してのみ行われるため、最終的に提出する解答を間違えないよう注意してください。
テストケース数
- 暫定テスト: 50個
-
システムテスト: 3000個
- システムテストでは、C は \{ 1,2,4,8,16,32,64,128 \} のそれぞれの値について、375個ずつのテストケースが存在します。
- コンテスト終了後に seeds.txt (sha256=
3bbc58026730d18fcb0e03ead929ab2afb6f9f0c5eb7f0c10ac44df4e6b84a3f) を公開します。
相対評価システムについて
暫定テスト・システムテストともに、CE以外の結果を得た一番最後の提出のみが順位表に反映されます。
相対評価スコアの計算に用いられる各テストケース毎の「全参加者中の最小消費体力」の算出には、各参加者の順位表に反映されている提出のみが用いられます。
順位表に表示されるスコアは相対評価スコアであり、新規提出があるたびに相対評価スコアが再計算されます。 一方、提出一覧から確認できる各提出のスコアは、各テストケース毎の消費体力をそのまま足し合わせたものであり、相対評価スコアは表示されません。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要となります。
不正な出力や制限時間超過をした場合、提出一覧から確認できるスコアは0となりますが、順位表には正解したテストケースに対する相対評価スコアの和が表示されます。
実行時間について
実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。
入出力
※この問題はインタラクティブ形式です。以下の内容を読み、ジャッジプログラムとのやり取りを行ってください。
最初に、入力が以下の形式で標準入力から与えられます。
\(
N ~ W ~ K ~ C \\
a_0 ~ b_0 \\
\vdots \\
a_{W-1} ~ b_{W-1} \\
c_0 ~ d_0 \\
\vdots \\
c_{K-1} ~ d_{K-1}\)
-
1行目には4つの整数 N,W,K,C がスペース区切りで与えられます。
- N は土地のサイズを表し、 N = 200 です。
- W は水源の数を表し、 1 \leq W \leq 4 を満たします。
- K は家の数を表し、 1 \leq K \leq 10 を満たします。
- C は体力の消費に関係するパラメータで、 C \in \{ 1,2,4,8,16,32,64,128 \} を満たします。
-
続く W+K 行には、水源と家が存在するセルの位置を表す2つの整数がスペース区切りで与えられます。
- 最初に、 W 行で与えられる2整数 a_i, b_i は、 セル (a_i, b_i) に水源が存在することを表します。0 \leq a_i \lt N, 0 \leq b_i \lt N を満たします。
- 続いて、 K 行で与えられる2整数 c_i, d_i は、 セル (c_i, d_i) に家が存在することを表します。0 \leq c_i \lt N, 0 \leq d_i \lt N を満たします。
- 全ての水源同士のペア・全ての家同士のペア・全ての水源と家のペアは、マンハッタン距離で \mathrm{round}(400/(W+K)) 以上離れていることが保証されます。
ここまでの入力を受け取った後は、掘削をどのように実行するかを以下の形式で標準出力へ出力してください。
\(y ~ x ~ P\)
-
1行目に3つの整数 y,x,P をスペース区切りで出力します。
- セル (y,x) に対して、パワー P で掘削を行います。
- セル (y,x) の岩盤はまだ破壊されていない必要があり、かつ、1 \leq P \leq 5000 を満たす必要があります。そうしなかった場合、WA となります。
- 出力の後には改行をし、標準出力をflushする必要があります。そうしなかった場合、TLE となる可能性があります。
出力後、掘削を実行した結果が入力として以下の形式で標準入力から与えられます。
\(r\)
-
1行に1つの整数 r が与えられます。
- 指定したセルの岩盤が破壊できなかった場合は
0となります。 - 指定したセルの岩盤が破壊できた場合、家が存在するセルでまだ水が流れていないものがあるならば
1、家が存在する全てのセルに水が流れているならば2となります。 - 不正な出力だった場合は
-1となります。
- 指定したセルの岩盤が破壊できなかった場合は
- r \in \{-1, 2\} の場合は、直ちにプログラムを終了してください。そうしなければ、TLE となる可能性があります。
- r \in \{0, 1\} の場合は、家が存在するセルでまだ水が流れていないものがあるため、引き続き掘削を行う必要があります。r \in \{-1, 2\} となるまで、掘削をどのように実行するかを繰り返し出力し、繰り返し入力を受け取ってください。
入力生成方法
L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(L,U) で、L 以上 U 以下の実数値を一様ランダムに生成する関数を \mathrm{randf}(L,U) で、b の p 乗を返す関数を \mathrm{pow}(b,p) で表す。
S_{i,j} の生成
-
乱数シード seed を元に、 -1.0以上1.0以下の範囲にスケーリングされた二次元の Perlin noise を生成する関数を \mathrm{noise}(y,x,seed) で表す。
以下のようにパラメタを選ぶ。- f0 = \mathrm{randf}(2.0,8.0)
- f1 = \mathrm{randf}(10.0,20.0)
- dy0 = \mathrm{randf}(0.0,1.0)
- dy1 = \mathrm{randf}(0.0,1.0)
- dx0 = \mathrm{randf}(0.0,1.0)
- dx1 = \mathrm{randf}(0.0,1.0)
- seed0 = \mathrm{rand}(0,2^{32} - 1)
- seed1 = \mathrm{rand}(0,2^{32} - 1)
- S_{i,j} = 1.0 / (1.0 + \mathrm{exp}(-3.0 \times (S_{i,j} - 0.25))) と更新する。（ロジスティック関数で変換をしている）
- p = \mathrm{randf}(2.0,4.0) を選ぶ。 S_{i,j} = \mathrm{pow}(S_{i,j},p) と更新する。
-
S_{i,j} を、 10 以上 5000 以下の範囲に線形スケーリングする。
すなわち、 S_{i,j}（ 0 \leq i, j \lt N ）の中で最小の値を l, 最大の値を u としたとき、 S_{i,j} = \mathrm{round}((S_{i,j} - l) \times (5000 - 10) / (u - l) + 10) と更新する。
水源と家の位置の生成
- W = \mathrm{rand}(1,4), K = \mathrm{rand}(1,10) とする。
- W 箇所の水源の位置(a_i, b_i), K 箇所の家の位置(c_i, d_i) を、それぞれ独立に、N ^ 2 個のセルの中から S_{i,j}に反比例する確率で選ぶ。
- W+K 箇所の位置の中にマンハッタン距離が \mathrm{round}(400/(W+K)) 未満の組がある場合、2. からやり直す。
C の生成
C = \mathrm{pow}(2,\mathrm{rand}(0,7)) と生成する。
必ずしも理解する必要はありません。
厳密な実装は入力ジェネレータのソースコードをご覧ください。
ツール（入力ジェネレータ・ビジュアライザ・ローカルテスタ・サンプルコード）
- Web版: アニメーション表示が可能です。
- ローカル版: 使用するにはRust言語のコンパイル環境をご用意下さい。
- Windows用のコンパイル済みバイナリ: Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。
- サンプルコード（C++, Python）: サンプルの解答です。次の処理を実装しています。
- それぞれの家について、一つ目の水源まで最短距離でまっすぐに掘削を行う
- パワーは常に
100に設定する - ジャッジプログラムから
2が返されたら、消費体力を標準エラー出力に出力して終了する
コンテスト終了までビジュアライズ結果の共有は禁止されています。ご注意下さい。
ツールで用いられる入出力ファイルの仕様
ローカルテスタに与える入力ファイルは以下の形式を用いています。
\(
N ~ W ~ K ~ C \\
S_{0,0} ~ \cdots ~ S_{0,N-1} \\
\vdots \\
S_{N-1,0} ~ \cdots ~ S_{N-1 ,N-1} \\
a_0 ~ b_0 \\
\vdots \\
a_{W-1} ~ b_{W-1} \\
c_0 ~ d_0 \\
\vdots \\
c_{K-1} ~ d_{K-1} \)
S_{i,j} はセル (i, j) にある岩盤の頑丈さの初期値です。
ローカルテスタは解答プログラムの出力をそのまま出力ファイルに書き出します。
解答プログラムは、# から始まるコメント行を出力に含めてもかまいません。
Web版ビジュアライザを使用すると、コメント行を対応する掘削と合わせて表示できるため、デバッグや考察等に役立てることができます。
ジャッジプログラムはコメント行を全て無視するため、コメント行を出力するプログラムをそのまま提出可能です。
入出力例
| Input | Output | 説明 |
|---|---|---|
3 1 1 128 0 0 1 1 |
入力の制約を満たさない、説明用の入力である点に注意してください。 3 \times 3 のグリッドで表される土地の (0,0) に水源が存在し、 (1,1) に家が存在します。 |
|
0 0 872 |
セル (0,0) に対して、パワー 872 で掘削をします。この際、体力を128+872 = 1000 消費します。 | |
0 |
この掘削では、セル (0,0) の岩盤は壊れませんでした。 ですが、セル (0,0) の岩盤の頑丈さは 872 減りました。 |
|
0 0 2 |
セル (0,0) に対して、パワー 2 で掘削をします。この際、体力を128+2 = 130 消費します。 | |
1 |
この掘削で、セル (0,0) の岩盤が壊れました。 セル (0,0) に水が流れるようになります。 |
|
1 1 872 |
セル (1,1) に対して、パワー 872 で掘削をします。この際、体力を128+872 = 1000 消費します。 | |
1 |
セル (1,1) の岩盤が壊れました。 |
|
1 0 872 |
セル (1,0) に対して、パワー 872 で掘削をします。この際、体力を128+872 = 1000 消費します。 | |
2 |
セル (1,0) の岩盤が壊れました。 セル (0,0), (1,0), (1,1) に水が流れるようになり、家が存在する全てのセルに水が流れるようになりました。 ジャッジプログラムから 2 が返されたら、直ちにプログラムを終了してください。消費した体力の合計である 1000+130+1000+1000 = 3130 が相対評価スコアの計算に用いられます。 |
Problem Statement
There is plot of land, represented by a grid of N rows and N columns.
On the grid, there are water sources in W spots, and houses in K spots.
Let us call the cell on ith ( 0 \leq i \lt N ) row from top and jth column ( 0 \leq j \lt N ) from left, (i, j).
Each cell (i, j) has an associated integer S_{i,j} between 10 and 5000 (inclusive), representing the sturdiness of the bedrock of the cell. The sturdiness is pre-determined, but it's not given as a part of the input.
When the bedrock of a cell containing a water source is crushed, water flows into the cell.
Furthermore, with cells with flowing water as starting points, water will flow horizontally and vertically into neighboring cells with crushed bedrock and span every cell it can reach this way.
X-san, who is in charge of the land, wants to crush bedrock to build watercourses to make the water flow into every cell with houses.
Please note that for water to flow into a cell with a house, the bedrock of that cell must be crushed too.
To crush bedrock, X-san repeatedly performs excavations as explained below.
- Choose a cell (i, j) whose bedrock isn't crushed yet, and a positive integer P less or equal than 5000, representing power.
- As C+P (C is a positive integer received as an input) of X-san's stamina gets consumed, the sturdiness S_{i,j} of the bedrock in the cell diminishes by P.
- If sturdiness then reaches zero S_{i,j} \leq 0, the bedrock of the cell (i, j) gets crushed.
Make the water flow into every cell with a house, while trying to conserve X-san's stamina as much as possible.
Scoring
For each test case, we compute the relative score \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}), where YOUR is your stamina consumption and MIN is the lowest stamina consumption among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.
The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases.
The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.
Number of test cases
- Provisional test: 50
-
System test: 3000
- For the system test, there will be 375 data inputs for each C (C \in \{ 1,2,4,8,16,32,64,128 \})
- We will publish seeds.txt (sha256=
3bbc58026730d18fcb0e03ead929ab2afb6f9f0c5eb7f0c10ac44df4e6b84a3f) after the contest is over.
About Relative Evaluation System
In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores.
The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the stamina consumption for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.
About execution time
Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percents compared to provisional tests. For these reasons, 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 make sure to have enough time margin for the execution.
Input and Output
Note: This problem is interactive. Read the following explanation, and communicate with the judge program accordingly.
At first, input will be provided via stdin in the following format.
\(
N ~ W ~ K ~ C \\
a_0 ~ b_0 \\
\vdots \\
a_{W-1} ~ b_{W-1} \\
c_0 ~ d_0 \\
\vdots \\
c_{K-1} ~ d_{K-1}\)
-
On the 1st row, there are four integers N,W,K,C separated by spaces.
- N represents the size of the plot and is N = 200.
- W represents the number of the water sources and satisfies 1 \leq W \leq 4.
- K represents the number of the houses and satisfies 1 \leq K \leq 10.
- C is a parameter related to stamina consumption and satisfies C \in \{ 1,2,4,8,16,32,64,128 \}.
-
The following W+K rows contain the coordinates of the cells containing water sources and houses, each expressed as a pair of space-separated integers.
- First W rows contain pairs of integers a_i, b_i, representing cells (a_i, b_i) that contain water sources. The integers satisfy 0 \leq a_i, b_i \lt N.
- Following K rows contain pairs of integers c_i, d_i, representing cells (c_i, d_i) that contain houses. The integers satisfy 0 \leq c_i, d_i \lt N.
- Each pair of water sources, each pair of houses and each pair of water sources and houses are guaranteed to be separated by at least Manhattan distance of \mathrm{round}(400/(W+K)).
After receiving the input this far, please output how to perform excavations to stdout in the following format.
\(y ~ x ~ P\)
-
On a single row, output three integers y,x,P separated by spaces.
- An excavation will be performed at cell (y,x) with power P.
- The bedrock on cell (y,x) must not be crushed yet, and power must satisfy 1 \leq P \leq 5000. If these conditions are not met, the result will be WA.
- You must output a newline after the integers, and flush stdout. If you don't, the result might turn out to be TLE.
After the output, the result of the performed excavation will be provided as an input in the following format.
\(r\)
-
On a single row, there is a single integer r.
- If the bedrock of the designated cell doesn't get crushed, r will be
0. - If the bedrock of the designated cell gets crushed; in case there are still cells with houses without flowing water, r will be
1, and in the case every cell with a house has flowing water, r will be2. - In case of invalid output, r will be
-1.
- If the bedrock of the designated cell doesn't get crushed, r will be
- In case of r \in \{-1, 2\}, please exit the program immediately. If you fail to do so, the result might turn out to be TLE.
- In case of r \in \{0, 1\}, there still exists cells with houses without flowing water; in that case, you need to continue performing excavations. Please continue receiving input and providing output how to perform excavations until r \in \{-1, 2\}.
Input Generation
Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive, and \mathrm{randf}(L,U) be a function that generates a uniform random real number between L and U, inclusive, and \mathrm{pow}(b,p) be a function that returns b to the power of p.
Generating S_{i,j}
-
Let \mathrm{noise}(y,x,seed) be a function that generates two-dimensional Perlin noise scaled to range -1.0 - 1.0, inclusive, according to a random seed seed.
Select parameters as the following.
- f0 = \mathrm{randf}(2.0,8.0)
- f1 = \mathrm{randf}(10.0,20.0)
- dy0 = \mathrm{randf}(0.0,1.0)
- dy1 = \mathrm{randf}(0.0,1.0)
- dx0 = \mathrm{randf}(0.0,1.0)
- dx1 = \mathrm{randf}(0.0,1.0)
- seed0 = \mathrm{rand}(0,2^{32} - 1)
- seed1 = \mathrm{rand}(0,2^{32} - 1)
- Update S_{i,j} = 1.0 / (1.0 + \mathrm{exp}(-3.0 \times (S_{i,j} - 0.25))). (Transformation by logistic function.)
- Select p = \mathrm{randf}(2.0,4.0). Update S_{i,j} = \mathrm{pow}(S_{i,j},p).
-
Scale S_{i,j} linearly to range 10 - 5000, inclusive.
I.e. let l be minimum and u be maximum of S_{i,j} ( 0 \leq i, j \lt N ), and update S_{i,j} = \mathrm{round}((S_{i,j} - l) \times (5000 - 10) / (u - l) + 10).
Generating the locations of water sources and houses
- Let W = \mathrm{rand}(1,4), K = \mathrm{rand}(1,10).
- Choose the coordinates (a_i, b_i) of the W water sources and the coordinates (c_i, d_i) of the K houses independently from the N ^ 2 cells with a probability inversely proportional to S_{i,j}.
- In case the Manhattan distance between any pairs of the W+K coordinates is under \mathrm{round}(400/(W+K)), go back to step 2 and regenerate.
Generating C
Given by C = \mathrm{pow}(2,\mathrm{rand}(0,7)).
You are not required to understand this.
Please refer to the source code of the input generator for implementation details.
Tools (Input generator, visualizer, local tester, and sample code)
- Web Version: For displaying animated visualizations.
- Local Version: Please set up a Rust language build environment to use this.
- Pre-compiled binary for Windows: If you have troubles setting up Rust environment, use this.
- Sample code (C++, Python): Sample answers. Implemented as follows:
- Performs excavations to build watercourses from the first water source to each house by the shortest, direct route.
- Uses constantly
100as the power setting. - Once the judge program returns
2, prints the consumed stamina to stderr and exits.
Note that sharing visualization results is forbidden until the contest ends.
Input format used in the tools
The input file for the local tester uses the following format.
\(
N ~ W ~ K ~ C \\
S_{0,0} ~ \cdots ~ S_{0,N-1} \\
\vdots \\
S_{N-1,0} ~ \cdots ~ S_{N-1 ,N-1} \\
a_0 ~ b_0 \\
\vdots \\
a_{W-1} ~ b_{W-1} \\
c_0 ~ d_0 \\
\vdots \\
c_{K-1} ~ d_{K-1} \)
S_{i,j} is the sturdiness value of the bedrock on cell (i, j).
The local tester writes outputs from your program directly to the output file.
Your program may output comment lines starting with #. The web version of the visualizer displays the comment lines with the corresponding excavations, which may be useful for debugging and analysis.
Since the judge program ignores all comment lines, you can submit a program that outputs comment lines as is.
I/O Examples
| Input | Output | Explanation |
|---|---|---|
3 1 1 128 0 0 1 1 |
Please note that this input is for explanation purposes, and thus doesn't meet all of the guarantees for input. On a 3 \times 3 grid, there exists a water source on cell (0,0), and a house on cell (1,1). |
|
0 0 872 |
An excavation is performed at cell (0,0) with power 872. Accordingly, stamina is consumed by 128+872 = 1000. | |
0 |
This excavation doesn't manage to crush the bedrock on cell (0,0). However, the sturdiness of the bedrock on cell (0,0) diminishes by 872. |
|
0 0 2 |
An excavation with power 2 is performed at cell (0,0). Accordingly, stamina is consumed by 128+2 = 130. | |
1 |
This excavation manages to crush the bedrock at cell (0,0). Water flows into cell (0,0). |
|
1 1 872 |
An excavation with power 872 is performed at cell (1,1). Accordingly, stamina is consumed by 128+872 = 1000. | |
1 |
The bedrock on cell (1,1) gets crushed. |
|
1 0 872 |
An excavation with power 872 is performed at cell (1,0). Accordingly, stamina is consumed by 128+872 = 1000. | |
2 |
The bedrock on cell (1,0) gets crushed. Water is now flowing into cells (0,0), (1,0) and (1,1), and every cell with a house now has flowing water. As the judge program now returns 2, please exit the program immediately.The sum of the consumed stamina, which turns out to be 1000+130+1000+1000 = 3130, is used to calculate the relative score. |
Time Limit: 0 msec / Memory Limit: 1024 MB