问题陈述
X先生有一个大农场,其中包括 N \times N 方块。
我们称该广场为 r从顶部开始的第 1 行 c左起第 列作为区域 (r, c) (0≤r, c<N).
M 未来农场里的蔬菜会生长并死亡 T 天。
的
树的 i-第蔬菜由五个整数表示 R_{i},C_{i},S_{i},E_{i}, 和 V_{i}.
他们的意思是具有以下价值的蔬菜 V_{i} 将出现在该区域 (R_{i},C_{i}) 上 S_{i}- 第天,并在结束时消失 E_{i}第一天。
X 用收割机收割这些蔬菜。
起初,他没有任何收割机,并且有 1 货币单位。
在每个 T 天,X 做出以下操作之一。
- 购买
- X 获得一台新的收割机,并将其放在没有另一台收割机的区域中。
- 当 X 有 j 收割机、采购成本 (j+1)^3 货币单位。
- 例如首次进货费用 1 货币单位。第二次购买费用 8 货币单位,等等。
- X 如果没有足够的钱就无法购买机器。
-
移动
- X 选择一台收割机并将其移动到没有收割机的区域之一。
-
通过
- X 不执行任何操作。
之后 t-th (0≤t<T) 行动时,以下事情按顺序发生。
- 对于所有我在哪里 S_{i} = t, 蔬菜 i 出现在该区域 (R_{i},C_{i}).
- 在有收获机的地区收获蔬菜。
- 对于每种蔬菜,让 v 为其值,并且 k 是具有包含蔬菜位置的收割机区域的 4 个连通分量的大小。
- 4 连通分量是通过垂直或水平相邻区域相互连接的区域组。
- X 收入 v \times k 货币单位。
- 这种蔬菜消失了。 如果尚未收获,
- 对于每种蔬菜,让 v 为其值,并且 k 是具有包含蔬菜位置的收割机区域的 4 个连通分量的大小。
你的目标是在他赚到尽可能多的钱之后 T-1- 第一天,确定 X 将采取的行动。
评分
测试用例的分数是 X 在 T-1第一天。
提交的分数是每个测试用例的总分。
- 临时测试由 50 个测试用例组成。如果您得到的结果不是
AC对于一个或多个测试用例,提交的分数将为零。 - 系统测试由 1000 个测试用例组成。如果您得到的结果不是
AC对于某些测试用例,只有这些测试用例的分数为零。
由于执行时间会有一些差异,非常接近时间限制的提交可能会导致TLE在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。 我们将发布 种子.txt (md5=75031719692fe939fb105e7af16e31c8) 比赛结束后。
输入
输入是按以下格式从标准输入给出的。
第一行由三个整数组成 N,M,T 用空格分隔。接下来的每一个 M 行由五个以空格分隔的整数组成。
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第蔬菜出现,满足 0≤R_{i}<N, 0≤C_{i}<N.
- S_{i} 是一个整数,表示日期 i第蔬菜出现,并满足 S_{i}≤S_{i+1},0≤S_{i}<T.
- E_{i} 是一个整数,表示日期 i-th 蔬菜消失,并且满足 S_{i}≤E_{i}<T.
- V_{i} 是一个整数,表示 i-第蔬菜。有关详细信息,请参阅下面的“测试用例生成”部分。
- If (R_i, C_i)=(R_j, C_j) (i<j) ,那么 E_i<S_j。也就是说,出现在同一区域的蔬菜的生命周期不重叠。
输出
输出 T行。
i- 第行代表 X i- 第一个动作。
- 用于制作 购买,输出两个以空格分隔的整数。
- 将购买的收割机放置在该区域 (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.
测试用例生成
每种蔬菜的生成方式如下。
所有随机选择都是统一随机的。
有关确切的详细信息,请参阅测试用例生成器的源代码。
- l_{i} 从之间的整数中选择 0 和 20,包括在内。
- S_{i} 从之间的整数中选择 0 和 T-1-l_{i},包括在内。
- E_{i} is S_{i} + l_{i}.
- v_{i} 是从大于或等于的浮点数中选择的 0.0 且小于或等于 1.0+S_{i}/100.0.
- V_{i} is \text{floor}(2^{v_{i}}).
- \text{floor}(x) 表示不大于的最大整数 x.
已生成 M 蔬菜按元组字典顺序排序 (S_{i},R_{i},C_{i}).
示例输入
9 4 10 3 3 1 5 35 4 4 4 6 22 8 8 7 9 20 2 3 8 9 10
注意:此输入用于解释目的,不符合约束。
示例输出
3 3 -1 2 3 3 4 2 3 4 4 3 3 7 8 4 4 7 7 3 4 8 7 8 8 -1
| 输出 | 说明 | 收割机放置 | 货币兑换 |
|---|---|---|---|
3 3 |
X 购买了一台收割机 1 货币单位,并将其放置到该区域 (3,3). |
--------- --------- --------- ---o----- --------- --------- --------- --------- --------- |
1 -> 0 |
-1 |
X 不执行任何操作。 该区域出现蔬菜 (3,3) 并收获。 X 收入 35 \times 1 = 35 货币单位。 |
--------- --------- --------- ---o----- --------- --------- --------- --------- --------- |
0 -> 35 |
2 3 |
X 购买了一台收割机 8 单位金钱,并将其放置到该区域 (2,3). |
--------- --------- ---o----- ---o----- --------- --------- --------- --------- --------- |
35 -> 27 |
3 4 |
X 购买了一台收割机 27 单位金钱,并将其放置到该区域 (3,4). |
--------- --------- ---o----- ---oo---- --------- --------- --------- --------- --------- |
27 -> 0 |
2 3 4 4 |
X 移动位于 (2,3) 到该地区 (4,4). 之后,该区域出现蔬菜 (4,4) 并收获。 X 收入 22 \times 3 = 66 货币单位。 |
--------- --------- --------- ---oo---- ----o---- --------- --------- --------- --------- |
0 -> 66 |
3 3 7 8 |
X 移动位于 (3,3) 到该地区 (7,8). |
--------- --------- --------- ----o---- ----o---- --------- --------- --------o --------- |
66 -> 66 |
4 4 7 7 |
X 移动位于 (4,4) 到该地区 (7,7). |
--------- --------- --------- ----o---- --------- --------- --------- -------oo --------- |
66 -> 66 |
3 4 8 7 |
X 移动位于 (3,4) 到该地区 (8,7). |
--------- --------- --------- --------- --------- --------- --------- -------oo -------o- |
66 -> 66 |
8 8 |
X 购买了一台收割机 64 单位金钱,并将其放置到该区域 (8,8). 之后,该地区的一种蔬菜 (8,8) 已收获。 X 收入 20 \times 4 = 80 货币单位。 |
--------- --------- --------- --------- --------- --------- --------- -------oo -------oo |
66 -> 82 |
-1 |
X 不执行任何操作。 该地区的一种蔬菜 (2,3) 消失。 |
--------- --------- --------- --------- --------- --------- --------- -------oo -------oo |
82 -> 82 |
从此输出获得的分数是 82.
工具
我们为参赛者提供工具。它包含测试用例生成器、输出验证器、示例输入数据、解决方案可视化器和示例解决方案(C++、Python)。
展示台
- 该可视化工具在最新的桌面版本上进行了测试 谷歌浏览器 和 Mozilla 火狐浏览器。我们不保证它适用于所有浏览器。
- 此可视化工具上计算的分数并非比赛的实际分数。在 AtCoder 竞赛页面提交您的解决方案即可参加竞赛。
- 使用此可视化工具的风险由您自行承担。
该可视化工具也包含在参赛者工具中。