33OJ
登录 注册

#P17812. [ICPC 2019 Nanchang R] Resistance

[ICPC 2019 Nanchang R] Resistance

题目描述

最近,Sheep 迷上了一款名为《抵抗》的塔防游戏。但现在他卡在了第 99 关。他不知道该怎么办,希望得到你的帮助。

《抵抗》是一款塔防游戏。游戏使用的地图是一个 n×nn \times n 的网格。一条由若干个格子组成的特定路径被给出,路径中任意两个相邻的格子共享一条公共边。我们保证该路径绝不重复经过同一个格子。一座村庄位于路径的终点。一些邪恶的入侵者将从起点登陆,沿着路径前进,并试图入侵村庄。

为了保护村庄,Sheep 在地图上部署了 kk 座防御塔来攻击入侵者。所有防御塔都布置在某些位置,但既不在路径上,也不在起点或终点。所有防御塔可分为两种:机枪塔和火焰喷射塔。

机枪塔装备有机枪,其有效射程可达 r1r_1。正常情况下,它会选择射程内最近的目标开火,对其目标造成 d1d_1 点伤害。如果存在多个最近的敌人(具有相同的最小欧几里得距离),则选择沿着路径到达村庄所需步数最少的那个。游戏规则保证此后不会再有歧义。攻击之后,机枪需要 t1t_1 帧时间重新装填弹药,因此如果它在第 xx 帧开火,则直到第 (x+t1)(x+t_1) 帧才能再次使用。

火焰喷射塔装备有火焰喷射器,其有效射程可达 r2r_2。它可以随时开火,没有类似机枪塔的限制。它也会按照与上述相似的条件选择目标。一次攻击将对其目标造成 d2d_2 点伤害,并且被攻击的入侵者将在下一帧开始燃烧。在入侵者燃烧的每一帧,它都会承受 d3d_3 点伤害。如果它在第 xx 帧被火焰喷射塔击中,则火焰将在第 (x+t2)(x+t_2) 帧结束时熄灭。此外,如果一个正在燃烧的入侵者再次被火焰喷射塔击中,假设它在第 yy 帧被击中,其燃烧时间将延长至第 (y+t2)(y+t_2) 帧结束。

现在游戏开始。总共会有 EE 个入侵者,第 ii 个入侵者将在第 ii 帧开始时从起点登陆。此后,任何入侵者每一帧都会沿着路径向前走一步。所有入侵者也可分为两种:列兵和上尉。

列兵是最低等的战士,没有特殊能力,其初始生命值为 HP1HP_1。

上尉则强大得多,其初始生命值为 HP2HP_2,并拥有某个等级的防御能力 defdef。一旦受到防御塔造成的伤害值为 damagedamage 的攻击,他将承受 max⁡{1,damage−def}\max\{1, damage - def\} 点伤害。注意,同一帧内来自不同防御塔的攻击应分别计算,但燃烧造成的伤害不计入防御能力范畴内的攻击。

生命值低于零的入侵者被视为死亡,并将被移除。

让我们总结一下游戏每一帧内会发生什么。

  • 敌方步进:所有存活的入侵者沿着路径向前走一步。然后,一名新的入侵者可能会从起点登陆。
  • 开火步进:所有防御塔选择各自的目标。然后它们同时开火,而那些需要等待目标或等待装填弹药的防御塔不进行任何动作。
  • 伤害结算:计算伤害值并扣除所有入侵者的生命值。此时燃烧伤害也会被一并计算。
  • 结束步进:所有生命值为负的入侵者被移除。如果一名存活的入侵者正停留在路径的终点,他将成功入侵村庄,并同样从游戏中被移除。

Sheep 已经了解到了一些关于来袭入侵者的细节,他要求你编写一个程序来模拟游戏最初 TT 帧的情况。

输入格式

测试数据包含多个测试用例,输入的第一行包含一个整数 TcaseTcase (Tcase≤10Tcase\le 10),表示测试用例的数量。

对于每个测试用例,第一行包含五个整数 n,k,L,En, k, L, E 和 TT,分别表示地图大小、防御塔数量、路径长度、入侵者数量以及你所模拟的帧数。保证所有测试用例中 E≤TE\le T。

接下来的 LL 行描述路径。其中第 ii 行包含两个整数 xix_i 和 yiy_i,描述路径上第 ii 个格子的坐标。我们保证路径中任意两个相邻格子共享一条公共边。位于 (x1,y1)(x_1,y_1) 的第一个格子是起点,位于 (xL,yL)(x_L,y_L) 的最后一个格子是终点,即村庄所在处。

接下来一行包含七个整数 r1,d1,t1,r2,d2,t2r_1, d_1, t_1, r_2, d_2, t_2 和 d3d_3,表示上述所有关于防御塔的参数。再接下来一行包含三个整数 HP1,HP2HP_1, HP_2 和 defdef,描述关于入侵者的参数。

接下来的 kk 行描述所有防御塔。其中第 ii 行包含三个整数 typei,xitype_i, x_i 和 yiy_i,(xi,yi)(x_i,y_i) 是第 ii 座防御塔的坐标,若 typei=1type_i=1 则该塔为机枪塔,若 typei=2type_i=2 则为火焰喷射塔。

最后一行包含一个长度为 EE 的字符串,其中的第 ii 个字符描述了第 ii 个入侵者的类型,我们使用字符 1 表示列兵,2 表示上尉。

输入中的所有数字均为正整数且不超过 400400。

输出格式

对于第 ii 个测试用例,首先在一行中输出 Case #i:(不含引号)。然后输出 EE 行,描述所有入侵者的最终状态。

其中第 ii 行对应于第 ii 个入侵者:

  • 如果他将成功入侵村庄,输出 Arrive with Y HP(s).(不含引号),其中 Y 表示他剩余的生命值。
  • 如果他将在第 tt 帧被击杀,输出 Be killed in the t-th frame at (x,y).(不含引号),其中 (x,y)(x,y) 描述他最终倒下的位置。
  • 如果该入侵者存活至第 TT 帧但未抵达村庄,输出 Be alive at (x,y) with Y HP(s).(不含引号),其中 (x,y)(x,y) 表示他在第 TT 帧的最终坐标,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 完成