← 返回题目列表

AtCoder · asprocon10_a

A. 网格上的作物

中文机器翻译题面 查看原题

问题陈述

有一块长方形的土地,大小为 H \times W。 这块土地被分成正方形 块 尺寸 1 \times 1,并且块之间的一些边界由 水道。 土地的边界被栅栏包围,除了一个单一的 入口,这是进入或离开土地的唯一途径。 入口设置在单个街区的一侧。

你计划成长 农作物 在这片土地上。 种植或收割农作物时,您需要将农业机械从入口处移至您计划作业的街区。 然而,没有设置固定的路径作为机械的通道。

由于现在建立路径将是一项具有挑战性的任务,因此您决定将机械移动到当前未用于种植农作物的区块中。 换句话说,在特定区块中种植或收获农作物时,必须能够从入口到达该区块,同时满足以下条件:

  • 每个方块只能移动到相邻的四个方块(不允许斜向移动)。
  • 如果两个街区被水路隔开,你就无法从一个街区移动到另一个街区。
  • 你不能穿过当前用于种植农作物的方块。

有 K 可供种植的农作物种类,编号 1, 2, \dots, K。 你要选择其中一些在下面种植和收获 T 个月。 种植农作物 k,你需要种植它 不迟于 这 S_k第一个月,收获吧 at 这 D_k- 第一个月。 你可以种植庄稼 k 之前 S_k- 第一个月,但即使你比要求的时间早种植,你也不能提前收获 D_k- 第一个月。

任意区块中允许种植任意种类的农作物,但多个区块中不能种植一种农作物,单个区块中不能种植多种农作物。

请制定一个使土地利用率最大化的种植计划。

土地详情

该土地的西北角坐标为 (0, 0),西南角 (H, 0),东北角 (0, W),以及东南角 (H, W)。 该街区位于 i+1从北数第 3 行和 j+1从西数第 列是一个带有对角点的正方形 (i, j) 和 (i + 1, j + 1)。 这个正方形称为块 (i, j) (0 \le i \le H - 1, 0 \le j \le W - 1).

入口设置在街区西侧 (i_0, 0) (即,在坐标之间的线段上 (i_0, 0) 和 (i_0 + 1, 0)).

对于共享边的块,它们之间是否有水路由给定的输入确定。 水路输入格式详见“输入”部分。

种植计划详情

种植计划描述了哪些作物种植在哪些区块上以及何时种植。 它由一个序列表示 (k_1, i_1, j_1, s_1), \dots, (k_M, i_M, j_M, s_M)。 的 m该序列的第一个元素表示作物 k_m 种植在区块中 (i_m, j_m) 上 s_m- 第一个月。

根据给定的种植计划,对 t第一个月 (t = 1, 2, \dots, T).

  1. 开头 t第一个月,对于所有人 m 其中 s_m = t,裁剪 k_m 种植在区块中 (i_m, j_m)。在此过程中, (i_m, j_m) 必须可以从入口到达,而无需穿过水道或穿过目前正在种植农作物的区块。
  2. 结束时 t第一个月,对于所有人 m 其中 D_{k_m} = t,裁剪 k_m 是从区块中收获的 (i_m, j_m)。在此过程中, (i_m, j_m) 必须可以从入口到达,而无需穿过水道或穿过目前正在种植农作物的区块。

当在同一个月种植多种作物时,上述可达性条件可能取决于作物的种植顺序。 例如,如果农作物 k_1 和 k_2 将在同一个月种植,并且 (i_2, j_2) 不经过就无法到达 (i_1, j_1),然后种植作物 k_1 之前 k_2 挡住了种植的路 k_2.

在这种情况下,如果存在订单并且按订单种植不会导致上述情况,则认为种植计划有效。 这样的顺序将由判断程序计算出来,因此不必在输出中确定。 同样,当在同一个月内收获多种农作物时,农作物的顺序将由判断程序计算出来,而不必在输出中确定。

种植计划必须满足以下条件。

  • 相同的作物只能种植在同一个区块中。
  • 一个块最多只能同时包含一种作物。
  • 种植农作物时 k,必须在之前种植 S_k- 第一个月。
  • 种植或收获农作物时,目标农作物必须能够从入口到达。

请注意,不需要种植所有 K 农作物。

评分

作物得分 k, X_k,按以下规则确定。

  1. 如果裁剪 k 没有被种植,那么 种植 X_k = 0.
  2. 如果裁剪 k ,然后 X_k = D_k - S_k + 1.

对于每个收到的测试用例 AC 判决,测试用例的分数将为 10^6 \times {\sum_{k = 1}^K X_k \over HWT} (在临时测试和系统测试中使用的所有测试用例中,该数字将为整数)。 对于每个未收到的测试用例 AC 判决,测试用例的分数将为 0.

在临时测试中,如果提交收到 AC 在所有测试用例中,提交的分数将是所有测试用例分数的总和。否则,提交的分数将是 0.

系统测试时,提交的分数将为所有测试用例分数的总和。

最终排名将由赛后进行的系统测试决定。 系统测试将仅对最后一次提交的结果进行,该提交的结果不是 CE。 最后提交时请注意不要出错。

测试用例数量

  • 临时测试:50
  • 系统测试:2000;我们将发布 种子.txt (sha256=0c2ffe8037c0c232ed9775b89a892fc1f68709a1582c83fd6bb609244cefcf32) 比赛结束后。

系统测试中的测试用例包含与 d = 1, 2, 3, 4,其中 d 是生成水路时使用的参数(具体参见输入生成)。

关于执行时间

每次运行的执行时间可能略有不同。此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。


输入

输入由标准输入按以下格式给出:

T H W i_0
h_{0, 0}h_{0, 1}\cdots h_{0, W-1}
\vdots
h_{H-2, 0}h_{H-2, 1}\cdots h_{H-2, W-1}
v_{0, 0}v_{0, 1}\cdots v_{0, W-2}
\vdots
v_{H-1, 0}v_{H-1, 1}\cdots v_{H-1, W-2}
K
S_1 D_1
\vdots
S_K D_K

h_{i, 0} \cdots h_{i, W-1} 是一个长度为的字符串 W 仅包含 0 和 1。 对于块 (i, j),如果南侧有水路(沿着坐标之间的线段) (i + 1, j) 和 (i + 1, j + 1)),然后 h_{i, j} = 1。 否则,如果没有水路, h_{i, j} = 0.

v_{i, 0} \cdots v_{i, W-2} 是一个长度为的字符串 W - 1 仅包含 0 和 1。 对于块 (i, j),如果东侧有水路(沿着坐标之间的线段) (i, j + 1) 和 (i + 1, j + 1)),然后 v_{i, j} = 1。 否则,如果没有水路, v_{i, j} = 0.

临时测试和系统测试的输入是通过下面“输入生成”中描述的方法生成的。 输入满足以下规定。

  • T = 100
  • H = W = 20
  • 0 \le i_0 \le H - 1
  • 0 < K \le HWT
  • 1 \le S_k < D_k \le T \quad (1 \le k \le K)
  • 对于任何特定的街区,可以通过在相邻街区之间移动而无需穿过水路从入口到达它。

输出

设要种植的农作物数量为 M, k_1, \dots, k_M 是要种植的作物的任意顺序,并且作物 k_m 计划种植于区块 (i_m, j_m) 在 s_m- 第一个月。

在这种情况下,按以下格式输出到标准输出 (stdout)。

M
k_1 i_1 j_1 s_1
\vdots
k_M i_M j_M s_M

输出必须满足问题陈述中描述的要求。 否则,测试用例将被判断为 WA.

输入生成

详情

让 \mathrm{rand}(L, U) 是生成至少L且小于U的均匀随机浮点数的函数。 让 \mathrm{normal}(\mu, \sigma^2) 是一个生成随机值的函数 标准正态分布 与 \mu 作为其平均值和 \sigma^2 作为其方差。

  • T = 100
  • H = W = 20
  • 生成 i_0 随机从 {0, 1, \dots, H - 1}.
  • 让 G = (V, E) 是以陆地(包括边界)上的格点为顶点、长度为线段的无向图 1 连接两个格点作为其边。正式地, V 和 E 定义如下:
    • V = \lbrace(i, j) \mid 0 \le i \le H, 0 \le j \le W\rbrace
    • E = \lbrace((i_1, j_1), (i_2, j_2)) \in V \times V \mid |i_1 - i_2| + |j_1 - j_2| = 1\rbrace
  • 按以下方式生成水道。
    • d = 1 + (\mathit{seed} \bmod 4)
    • 标记所有位于边界上的顶点(即所有 (i, j) \in V 其中 i = 0, i = H, j = 0,或 j = W 已满足)。
    • 重复以下过程。
      • 让 V' 是被标记的顶点集,并且 V'' = \lbrace (i', j') \in V \mid \forall (i, j) \in V', |i - i'| + |j - j'| > d \rbrace.
      • If V'' 为空,水路生成过程结束。否则,让 (i, j) 是随机选择的元素 V''.
      • 让 (i', j') 是以下顶点 V' 最接近 (i, j)。如果有多个候选人 (i', j'),让 (i', j') 随机成为其中之一。
      • 让 P 是最短路径 G 正在连接 (i, j) 和 (i', j')。如果有多个候选人 P,让 P 是具有最少转折点的路径之一。如果还有多个(最多 2) 的候选人 P,让 P 随机成为其中之一。
      • 将所有边缘设置为 P 至水路。
      • 标记所有顶点 P.
  • 让 L = \mathrm{round}(HWT \times \mathrm{rand(1.0, 2.0)})。对于 k = 1, 2, \dots,重复以下过程生成 D_k 和 S_k.
    • 让 L_k = \mathrm{round}(10^{\mathrm{normal}(1, 0.25^2)})。如果 2 \le L_k \le T 不满意,重新生成 L_k.
    • 生成 D_k 随机从 {L_k, L_k + 1, \dots, T}.
    • 让 S_k = D_k - L_k + 1.
    • If \sum_{i = 1}^k L_i \ge L,则流程结束。

工具

在比赛结束之前不允许共享可视化结果。


示例输入 1

10 6 6 3
011010
000001
011000
000110
011000
00000
10001
10010
00110
10101
10000
20
2 10
1 10
4 10
1 10
2 9
4 5
2 8
4 10
4 9
1 9
1 3
1 6
1 7
3 6
8 10
1 7
3 8
2 8
1 10
2 10

示例输出 1

12
1 0 0 2
2 0 1 1
3 1 0 4
4 0 2 1
5 3 1 2
6 2 0 4
7 4 0 2
10 3 2 1
15 2 0 8
18 5 0 2
19 0 3 1
20 4 1 2

该示例仅显示输入/输出的具体示例,并且小于用于评分的实际测试用例。