
问题陈述
有一块土地,由网格表示 N 行和 N 列。
网格上有 水源 in W 点,以及 房屋 in K 斑点。
让我们呼叫该单元 i日 ( 0 \leq i \lt N ) 从顶部行和 j第列( 0 \leq j \lt N )从左起, (i, j).
每个单元格 (i, j) 有一个关联的整数 S_{i,j} 之间 10 和 5000 (含),代表 坚固性 的 基岩
细胞的 。的 坚固性 是预先确定的,但它不是作为输入的一部分给出的。
当 基岩
细胞的 包含一个单元格 水源地 被压碎,水流入细胞。
此外,以流动水的单元格为起点,水会水平和垂直地流入具有压碎的相邻单元格中。 基岩
细胞的 并跨越它可以通过这种方式到达的每个单元格。
掌管这片土地的X桑想要粉碎 基岩
细胞的 建造水道,让水流进每一个细胞 房屋.
请注意,水要流入具有 房子
该细胞的, 基岩
细胞的 也必须被粉碎。
粉碎 基岩
细胞的,X桑反复表演 挖掘 如下所述。
- 选择一个单元格 (i, j) 谁的 基岩 细胞的 还没有被压垮,并且是一个正整数 P 小于或等于 5000,代表 电源 咒语的.
- As C+P (C 是 X-san 的作为输入接收的正整数) 耐力 被消耗, 细胞中的 坚固性 S_{i,j} 的 基岩 细胞的 减少 P.
- If 坚固性 然后达到零 细胞的 S_{i,j} \leq 0, 基岩 细胞的 细胞的 (i, j) 被压碎。
使水流进每个细胞 房子 该细胞的,同时努力保护X桑的 耐力 尽可能多。
评分
对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的耐力消耗,MIN 是在该测试用例中获得的所有竞争对手中最低的耐力消耗。提交的分数是相对分数的总和。
最终排名将通过比赛结束后进行的系统测试进行更多的输入来确定。 在临时/系统测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MIN 计算之外。
系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。
测试用例数量
- 临时测试:50
-
系统测试:3000
- 对于系统测试,每个系统将有 375 个数据输入 C (C \in \{ 1,2,4,8,16,32,64,128 \})
- 我们将发布 种子.txt (sha256=
3bbc58026730d18fcb0e03ead929ab2afb6f9f0c5eb7f0c10ac44df4e6b84a3f) 比赛结束后。
关于相关评价体系
在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MIN。
排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的体力消耗的总和,并且没有显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或确保有足够的执行时间。
输入和输出
注意:此问题是交互式的。阅读下面的解释,并与判断程序进行相应的沟通。
首先,将通过 stdin 按以下格式提供输入。
\(
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}\)
-
第一行有四个整数 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 行包含包含以下内容的单元格的坐标 水源 和 房屋,每个表示为一对空格分隔的整数。
- 第一 W 行包含整数对 a_i, b_i,代表单元格 (a_i, b_i) 包含 水源。整数满足 0 \leq a_i, b_i \lt N.
- 正在关注 K 行包含整数对 c_i, d_i,代表单元格 (c_i, d_i) 包含 房屋。整数满足 0 \leq c_i, d_i \lt N.
- 每对 水源,每对 房屋 和每对 水源 和 房屋 保证至少分开 曼哈顿距离 of \mathrm{round}(400/(W+K)).
收到到目前为止的输入后,请输出如何执行 挖掘 按以下格式发送到标准输出。
\(y ~ x ~ P\)
-
在单行上输出三个整数 y,x,P 以空格分隔。
- An 挖掘 将在单元格执行 细胞上的 (y,x) 与 电源 咒语的 P.
- 的 基岩 细胞的 在细胞上 (y,x) 还不能被压碎,并且 电源 咒语的 必须满足 1 \leq P \leq 5000。如果不满足这些条件,结果将是 WA.
- 您必须 在整数后输出换行符,并刷新标准输出。如果你不这样做,结果可能会是 TLE.
输出后,执行的结果 挖掘 将作为以下格式的输入提供。
\(r\)
-
在单行上有一个整数
指定单元格的 r.
- 如果 基岩
细胞的 没有被压碎, r 将是
指定细胞的
0. - 如果 基岩
细胞的 被压碎;如果仍然有细胞 房屋 没有流水, r 将是
指定细胞的
1,在这种情况下,每个单元格都有一个 房子 该细胞的 有流动的水, r 将是 指定细胞的2. - 如果输出无效, r 将是
指定细胞的
-1.
- 如果 基岩
细胞的 没有被压碎, r 将是
指定细胞的
- 如果 r \in \{-1, 2\},请立即退出程序。如果你不这样做,结果可能是 TLE.
- 如果 r \in \{0, 1\},仍然存在带有 房屋 无流水;在这种情况下,您需要继续执行 挖掘。请继续接收输入并提供输出如何执行 挖掘 直到 r \in \{-1, 2\}.
输入生成
让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包含在内,并且 \mathrm{randf}(L,U) 是一个生成均匀随机实数的函数 L 和 U,包含在内,并且 \mathrm{pow}(b,p) 是一个返回的函数 b 的幂 p.
生成 S_{i,j}
-
让 \mathrm{noise}(y,x,seed) 是一个生成二维的函数 柏林噪音 缩放至范围 -1.0 - 1.0,包含在内,根据随机种子 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,包括在内。
即让 l 是最小值并且 u 最大为 S_{i,j} ( 0 \leq i, j \lt N ),并更新 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).
- 选择坐标 (a_i, b_i) 的 W 水源地及坐标 (c_i, d_i) 的 K 房屋独立于 N ^ 2 单元格的概率与 S_{i,j}.
- 如果任意对之间的曼哈顿距离 W+K 坐标位于 \mathrm{round}(400/(W+K)),返回步骤2并重新生成。
生成 C
由以下给出 C = \mathrm{pow}(2,\mathrm{rand}(0,7)).
您不需要了解这一点。
请参阅输入生成器的源代码以了解实现细节。
工具(输入生成器、可视化工具、本地测试器和示例代码)
- 网页版:用于显示动画可视化。
- 本地版本:请设置 Rust 语言 构建使用此的环境。
- Windows 预编译二进制文件:如果您在设置 Rust 环境时遇到问题,请使用它。
- 示例代码(C++、Python):示例答案。实施如下:
- 执行 挖掘 从修建河道开始 水源地 给每个 房子 该细胞的 采用最短、直接的路线。
- 不断使用
100作为 电源 咒语的 设置。 - 一旦判断程序返回
2,打印消耗的 耐力 到 stderr 并退出。
请注意,在比赛结束之前禁止共享可视化结果。
工具中使用的输入格式
本地测试器的输入文件使用以下格式。
\(
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).
本地测试器将程序的输出直接写入输出文件。
您的程序可能会输出以以下内容开头的注释行 #。可视化工具的网络版本显示注释行以及相应的 挖掘,这对于调试和分析可能有用。
由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。
I/O 示例
| 输入 | 输出 | 说明 |
|---|---|---|
3 1 1 128 0 0 1 1 |
请注意,此输入仅用于解释目的,因此不满足所有输入保证。 在 3 \times 3 网格,存在一个 水源地 在细胞上 (0,0),和 房子 该细胞的 在细胞上 (1,1). |
|
0 0 872 |
An 挖掘 在单元格执行 (0,0) 与 电源 咒语的 872。据此, 耐力 被消耗 128+872 = 1000. | |
0 |
这个 挖掘 没能粉碎 基岩
细胞的 在细胞上 (0,0). 然而, 坚固性 的 基岩 细胞的 在细胞上 (0,0) 减少 872. |
|
0 0 2 |
An 挖掘 与 电源 咒语的 2 在单元格执行 (0,0)。据此, 耐力 被消耗 128+2 = 130. | |
1 |
这个 挖掘 设法粉碎 基岩
细胞的 在单元格 (0,0). 水流入细胞 (0,0). |
|
1 1 872 |
An 挖掘 与 电源 咒语的 872 在单元格执行 (1,1)。据此, 耐力 被消耗 128+872 = 1000. | |
1 |
的 基岩
细胞的 在细胞上 (1,1) 被压碎。 |
|
1 0 872 |
An 挖掘 与 电源 咒语的 872 在单元格执行 (1,0)。据此, 耐力 被消耗 128+872 = 1000. | |
2 |
的 基岩
细胞的 在细胞上 (1,0) 被压碎。 水现在流入细胞 (0,0), (1,0) 和 (1,1),每个单元格都有一个 房子 该细胞的 现在有流动的水。 由于判断程序现在返回 2,请立即退出程序。消耗的总和 耐力,结果是 1000+130+1000+1000 = 3130,用于计算相对分数。 |