问题陈述
有一块长方形的土地,大小为 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).
- 开头 t第一个月,对于所有人 m 其中 s_m = t,裁剪 k_m 种植在区块中 (i_m, j_m)。在此过程中, (i_m, j_m) 必须可以从入口到达,而无需穿过水道或穿过目前正在种植农作物的区块。
- 结束时 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,按以下规则确定。
- 如果裁剪 k 没有被种植,那么 种植 X_k = 0.
- 如果裁剪 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,则流程结束。
工具
- 网页版:显示动画时比本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果您不熟悉Rust语言环境,请改用它。
- 示例代码 (C++):此示例代码搜索一个块来种植每种农作物,并选择找到的第一个。 只有第一个 \min(K, 10) 作物被考虑。
在比赛结束之前不允许共享可视化结果。
示例输入 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
该示例仅显示输入/输出的具体示例,并且小于用于评分的实际测试用例。