P17812 [ICPC 2019 Nanchang R] Resistance

Recently, Sheep gets fascinated in a tower defense game called $Resistance$. But now he is stuck at the $99$-th level. He doesn't know what to do and hopes for your help. $Resistance$ is a tower defense game. The map used in this game is an $n\times n$. A specific path consisting of several cells is given in which any two adjacent cells share a common edge. We guarantee that the path never passes by a cell twice. A village is locating at the destination of the path. Some evil invaders will land at the starting point, go along the path and attempt to invade the village. To secure the village, Sheep has deployed $k$ defense towers in the map to attack invaders. All defense towers are lying at some locations but neither on the path nor at the starting point or the destination. All defense towers can be divided into two kinds: **gun towers** and **bunkers**. A gun tower is armed with the machine gun, whose effective range is up to $r_1$. Under normal circumstances, it selects the nearest target within the range and fire, causing $d_1$ damage points for its target. If there are more than one nearest enemies (with the same smallest Euclidean distance), the one who can reach the village with least steps on the path. The rules of the game guarantee that there wouldn't be more ambiguities. After an attack, the machine gun will need $t_1$ frames of time for reloading ammunition, so it would not be used again until the $(x+t_1)$-th frame if it fired at the $x$-th frame. A bunker is armed with a flame thrower, whose effective range is up to $r_2$. It can fire at every time without any restrictions like gun towers. It also selects a target satisfying the similar conditions as above. An attack will cause $d_2$ damage points for its target, and the attacked invader will start to burn in the next frame of time. At each frame when the invader is burning, it suffers from $d_3$ damage points. The fire will be quenched at the end of the $(x+t_2)$-th frame if was hit by a bunker at the $x$-th frame. Moreover, if a burning invader was hit by a bunker again, supposing that it was hit at the $y$-th frame, its burning time will be prolonged to the end of the $(y+t_2)$-th frame. Now the round starts. There will be $E$ invaders in total, the $i$-th of which will land at the starting point in the beginning of the $i$-th frame of time. After that, any invader will take a step forward along the path in each frame of time. All invaders can be also divided into two kinds: **privates** and **captains**. A private is the most inferior warrior with no special ability whose initial health point is $HP_1$. A captain is much more powerful whose initial health point is $HP_2$, with some level $def$ of defense capability. Once attacked by a defense tower whose damage point is $damage$, he will suffer from $\max\{1,damage-def\}$ damage point. Note that attacks from different defense towers in any frame should be considered separately, but the damage caused by burning will not be considered as an attack within the defense capability. An invader with health point less than zero is presumed dead and will be removed. Let's make a summary of what will happen in a frame of time in this game. - **The Enemy Step.** All alive invaders take a step forward along the path. Then, a new invader may land at the starting point. - **The Fire Step.** All defense towers select their target. Then they fire together while those defense towers which have to target or wait for reloading ammunitions do nothing. - **The Damage Estimation.** Calculate the damage points and deduce the health points of all invaders. The burning damage will also be calculated at this time. - **The Ending Step.** All invaders with negative health points will be removed. If an alive invader is staying at the destination of the path, he invades the village successfully and will also be removed from the game. Sheep has got some details about coming invaders, and he asks you to write a programme to simulate the game for the first $T$ frames of time.

The test data contains several test cases and the first line in input contains an integer $Tcase~(Tcase\le 10)$ representing the number of test cases. For every test case, The first line contains five integers $n, k, L, E$ and $T$ indicating the size of the map, the number of the defense towers, the length of the path, the number of invaders and the number of frames among your simulation. We guarantee that $E\le T$ in all cases. The following $L$ lines describe the path. The $i$-th of them contains two integers $x_i$ and $y_i$ describing the coordinate of the $i$-th cell in the path. We guarantee that any two adjacent cells in the path share a common edge. The first cell locating at $(x_1,y_1)$ is the starting point and the last cell locating at $(x_L,y_L)$ is the destination where the village is. The next line contains seven integers $r_1, d_1, t_1, r_2, d_2, t_2$ and $d_3$ indicating all parameters about defense towers described as above. And then a line containing three integers $HP_1,HP_2$ and $def$ describes parameters about invaders. The next $k$ lines describe all defense towers. The $i$-th of them contains three integers $type_i, x_i$ and $y_i$ where $(x_i,y_i)$ is the coordinate of the $i$-th defense tower, and if $type_i=1$ the tower is a gun tower, or a bunker if $type_i=2$. The last line contains a string of length $E$, the $i$-th digit in which describes the type of the $i$-th invader where we use the character `1` to represent a private, and `2` to represent a captain. All numbers in the input are positive integers and no more than $400$.

For the $i$-th test case, output `Case #i:` (without quotes) in the first line. Then output $E$ lines describing the final states of all invaders. The $i$-th line of them indicates the $i$-th invader: - If it will invade the village successfully, output `Arrive with Y HP(s).` (without quotes) where **Y** represents his remaining $HP$. - If it will be killed in the $t$-th frame, output `Be killed in the t-th frame at (x,y).` (without quotes), where $(x,y)$ describes the location of his final resting place. - If this invader will live up to the $T$-th frame but not arrive at the village, output `Be alive at (x,y) with Y HP(s).` (without quotes), where $(x,y)$ represents his final coordinate in the $T$-th frame and **Y** represents his remaining $HP$.