#P17812. [ICPC 2019 Nanchang R] Resistance
[ICPC 2019 Nanchang R] Resistance
题目描述
最近,Sheep 迷上了一款名为《抵抗》的塔防游戏。但现在他卡在了第 99 关。他不知道该怎么办,希望得到你的帮助。
《抵抗》是一款塔防游戏。游戏使用的地图是一个 的网格。一条由若干个格子组成的特定路径被给出,路径中任意两个相邻的格子共享一条公共边。我们保证该路径绝不重复经过同一个格子。一座村庄位于路径的终点。一些邪恶的入侵者将从起点登陆,沿着路径前进,并试图入侵村庄。
为了保护村庄,Sheep 在地图上部署了 座防御塔来攻击入侵者。所有防御塔都布置在某些位置,但既不在路径上,也不在起点或终点。所有防御塔可分为两种:机枪塔和火焰喷射塔。
机枪塔装备有机枪,其有效射程可达 。正常情况下,它会选择射程内最近的目标开火,对其目标造成 点伤害。如果存在多个最近的敌人(具有相同的最小欧几里得距离),则选择沿着路径到达村庄所需步数最少的那个。游戏规则保证此后不会再有歧义。攻击之后,机枪需要 帧时间重新装填弹药,因此如果它在第 帧开火,则直到第 帧才能再次使用。
火焰喷射塔装备有火焰喷射器,其有效射程可达 。它可以随时开火,没有类似机枪塔的限制。它也会按照与上述相似的条件选择目标。一次攻击将对其目标造成 点伤害,并且被攻击的入侵者将在下一帧开始燃烧。在入侵者燃烧的每一帧,它都会承受 点伤害。如果它在第 帧被火焰喷射塔击中,则火焰将在第 帧结束时熄灭。此外,如果一个正在燃烧的入侵者再次被火焰喷射塔击中,假设它在第 帧被击中,其燃烧时间将延长至第 帧结束。
现在游戏开始。总共会有 个入侵者,第 个入侵者将在第 帧开始时从起点登陆。此后,任何入侵者每一帧都会沿着路径向前走一步。所有入侵者也可分为两种:列兵和上尉。
列兵是最低等的战士,没有特殊能力,其初始生命值为 。
上尉则强大得多,其初始生命值为 ,并拥有某个等级的防御能力 。一旦受到防御塔造成的伤害值为 的攻击,他将承受 点伤害。注意,同一帧内来自不同防御塔的攻击应分别计算,但燃烧造成的伤害不计入防御能力范畴内的攻击。
生命值低于零的入侵者被视为死亡,并将被移除。
让我们总结一下游戏每一帧内会发生什么。
- 敌方步进:所有存活的入侵者沿着路径向前走一步。然后,一名新的入侵者可能会从起点登陆。
- 开火步进:所有防御塔选择各自的目标。然后它们同时开火,而那些需要等待目标或等待装填弹药的防御塔不进行任何动作。
- 伤害结算:计算伤害值并扣除所有入侵者的生命值。此时燃烧伤害也会被一并计算。
- 结束步进:所有生命值为负的入侵者被移除。如果一名存活的入侵者正停留在路径的终点,他将成功入侵村庄,并同样从游戏中被移除。
Sheep 已经了解到了一些关于来袭入侵者的细节,他要求你编写一个程序来模拟游戏最初 帧的情况。
输入格式
测试数据包含多个测试用例,输入的第一行包含一个整数 (),表示测试用例的数量。
对于每个测试用例,第一行包含五个整数 和 ,分别表示地图大小、防御塔数量、路径长度、入侵者数量以及你所模拟的帧数。保证所有测试用例中 。
接下来的 行描述路径。其中第 行包含两个整数 和 ,描述路径上第 个格子的坐标。我们保证路径中任意两个相邻格子共享一条公共边。位于 的第一个格子是起点,位于 的最后一个格子是终点,即村庄所在处。
接下来一行包含七个整数 和 ,表示上述所有关于防御塔的参数。再接下来一行包含三个整数 和 ,描述关于入侵者的参数。
接下来的 行描述所有防御塔。其中第 行包含三个整数 和 , 是第 座防御塔的坐标,若 则该塔为机枪塔,若 则为火焰喷射塔。
最后一行包含一个长度为 的字符串,其中的第 个字符描述了第 个入侵者的类型,我们使用字符 1 表示列兵,2 表示上尉。
输入中的所有数字均为正整数且不超过 。
输出格式
对于第 个测试用例,首先在一行中输出 Case #i:(不含引号)。然后输出 行,描述所有入侵者的最终状态。
其中第 行对应于第 个入侵者:
- 如果他将成功入侵村庄,输出
Arrive with Y HP(s).(不含引号),其中 Y 表示他剩余的生命值。 - 如果他将在第 帧被击杀,输出
Be killed in the t-th frame at (x,y).(不含引号),其中 描述他最终倒下的位置。 - 如果该入侵者存活至第 帧但未抵达村庄,输出
Be alive at (x,y) with Y HP(s).(不含引号),其中 表示他在第 帧的最终坐标,Y 表示他剩余的生命值。
2
5 1 5 3 8
2 1
2 2
2 3
2 4
2 5
2 5 1 2 5 1 1
8 8 2
1 1 3
111
5 1 5 3 3
2 1
2 2
2 3
2 4
2 5
2 5 1 2 5 1 1
8 8 2
1 1 3
111
Case #1:
Be killed in the 3-th frame at (2,3).
Arrive with 3 HP(s).
Be killed in the 6-th frame at (2,4).
Case #2:
Be killed in the 3-th frame at (2,3).
Be alive at (2,2) with 8 HP(s).
Be alive at (2,1) with 8 HP(s).
2
5 1 5 3 8
2 1
2 2
2 3
2 4
2 5
2 5 1 2 5 1 1
8 8 2
1 1 3
211
5 1 5 3 8
2 1
2 2
2 3
2 4
2 5
2 5 1 2 5 1 1
8 8 2
2 1 3
211
Case #1:
Arrive with 2 HP(s).
Arrive with 3 HP(s).
Be killed in the 6-th frame at (2,4).
Case #2:
Arrive with 0 HP(s).
Arrive with 2 HP(s).
Be killed in the 6-th frame at (2,4).
提示
翻译由 DeepSeek V4 Pro 完成