P17812 [ICPC 2019 Nanchang R] Resistance

最近，Sheep 迷上了一款名为《抵抗》的塔防游戏。但现在他卡在了第 99 关。他不知道该怎么办，希望得到你的帮助。 《抵抗》是一款塔防游戏。游戏使用的地图是一个 $n \times n$ 的网格。一条由若干个格子组成的特定路径被给出，路径中任意两个相邻的格子共享一条公共边。我们保证该路径绝不重复经过同一个格子。一座村庄位于路径的终点。一些邪恶的入侵者将从起点登陆，沿着路径前进，并试图入侵村庄。 为了保护村庄，Sheep 在地图上部署了 $k$ 座防御塔来攻击入侵者。所有防御塔都布置在某些位置，但既不在路径上，也不在起点或终点。所有防御塔可分为两种：**机枪塔**和**火焰喷射塔**。 机枪塔装备有机枪，其有效射程可达 $r_1$。正常情况下，它会选择射程内最近的目标开火，对其目标造成 $d_1$ 点伤害。如果存在多个最近的敌人（具有相同的最小欧几里得距离），则选择沿着路径到达村庄所需步数最少的那个。游戏规则保证此后不会再有歧义。攻击之后，机枪需要 $t_1$ 帧时间重新装填弹药，因此如果它在第 $x$ 帧开火，则直到第 $(x+t_1)$ 帧才能再次使用。 火焰喷射塔装备有火焰喷射器，其有效射程可达 $r_2$。它可以随时开火，没有类似机枪塔的限制。它也会按照与上述相似的条件选择目标。一次攻击将对其目标造成 $d_2$ 点伤害，并且被攻击的入侵者将在下一帧开始燃烧。在入侵者燃烧的每一帧，它都会承受 $d_3$ 点伤害。如果它在第 $x$ 帧被火焰喷射塔击中，则火焰将在第 $(x+t_2)$ 帧结束时熄灭。此外，如果一个正在燃烧的入侵者再次被火焰喷射塔击中，假设它在第 $y$ 帧被击中，其燃烧时间将延长至第 $(y+t_2)$ 帧结束。 现在游戏开始。总共会有 $E$ 个入侵者，第 $i$ 个入侵者将在第 $i$ 帧开始时从起点登陆。此后，任何入侵者每一帧都会沿着路径向前走一步。所有入侵者也可分为两种：**列兵**和**上尉**。 列兵是最低等的战士，没有特殊能力，其初始生命值为 $HP_1$。 上尉则强大得多，其初始生命值为 $HP_2$，并拥有某个等级的防御能力 $def$。一旦受到防御塔造成的伤害值为 $damage$ 的攻击，他将承受 $\max\{1, damage - def\}$ 点伤害。注意，同一帧内来自不同防御塔的攻击应分别计算，但燃烧造成的伤害不计入防御能力范畴内的攻击。 生命值低于零的入侵者被视为死亡，并将被移除。 让我们总结一下游戏每一帧内会发生什么。 - **敌方步进**：所有存活的入侵者沿着路径向前走一步。然后，一名新的入侵者可能会从起点登陆。 - **开火步进**：所有防御塔选择各自的目标。然后它们同时开火，而那些需要等待目标或等待装填弹药的防御塔不进行任何动作。 - **伤害结算**：计算伤害值并扣除所有入侵者的生命值。此时燃烧伤害也会被一并计算。 - **结束步进**：所有生命值为负的入侵者被移除。如果一名存活的入侵者正停留在路径的终点，他将成功入侵村庄，并同样从游戏中被移除。 Sheep 已经了解到了一些关于来袭入侵者的细节，他要求你编写一个程序来模拟游戏最初 $T$ 帧的情况。

测试数据包含多个测试用例，输入的第一行包含一个整数 $Tcase$ ($Tcase\le 10$)，表示测试用例的数量。 对于每个测试用例，第一行包含五个整数 $n, k, L, E$ 和 $T$，分别表示地图大小、防御塔数量、路径长度、入侵者数量以及你所模拟的帧数。保证所有测试用例中 $E\le T$。 接下来的 $L$ 行描述路径。其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，描述路径上第 $i$ 个格子的坐标。我们保证路径中任意两个相邻格子共享一条公共边。位于 $(x_1,y_1)$ 的第一个格子是起点，位于 $(x_L,y_L)$ 的最后一个格子是终点，即村庄所在处。 接下来一行包含七个整数 $r_1, d_1, t_1, r_2, d_2, t_2$ 和 $d_3$，表示上述所有关于防御塔的参数。再接下来一行包含三个整数 $HP_1, HP_2$ 和 $def$，描述关于入侵者的参数。 接下来的 $k$ 行描述所有防御塔。其中第 $i$ 行包含三个整数 $type_i, x_i$ 和 $y_i$，$(x_i,y_i)$ 是第 $i$ 座防御塔的坐标，若 $type_i=1$ 则该塔为机枪塔，若 $type_i=2$ 则为火焰喷射塔。 最后一行包含一个长度为 $E$ 的字符串，其中的第 $i$ 个字符描述了第 $i$ 个入侵者的类型，我们使用字符 `1` 表示列兵，`2` 表示上尉。 输入中的所有数字均为正整数且不超过 $400$。

对于第 $i$ 个测试用例，首先在一行中输出 `Case #i:`（不含引号）。然后输出 $E$ 行，描述所有入侵者的最终状态。 其中第 $i$ 行对应于第 $i$ 个入侵者： - 如果他将成功入侵村庄，输出 `Arrive with Y HP(s).`（不含引号），其中 **Y** 表示他剩余的生命值。 - 如果他将在第 $t$ 帧被击杀，输出 `Be killed in the t-th frame at (x,y).`（不含引号），其中 $(x,y)$ 描述他最终倒下的位置。 - 如果该入侵者存活至第 $T$ 帧但未抵达村庄，输出 `Be alive at (x,y) with Y HP(s).`（不含引号），其中 $(x,y)$ 表示他在第 $T$ 帧的最终坐标，**Y** 表示他剩余的生命值。

翻译由 DeepSeek V4 Pro 完成