33OJ
登录 注册

#P17812. [ICPC 2019 Nanchang R] Resistance

[ICPC 2019 Nanchang R] Resistance

Problem Description

Recently, Sheep gets fascinated in a tower defense game called ResistanceResistance. But now he is stuck at the 9999-th level. He doesn't know what to do and hopes for your help.

ResistanceResistance is a tower defense game. The map used in this game is an n×nn\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 kk 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 r1r_1. Under normal circumstances, it selects the nearest target within the range and fire, causing d1d_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 t1t_1 frames of time for reloading ammunition, so it would not be used again until the (x+t1)(x+t_1)-th frame if it fired at the xx-th frame.

A bunker is armed with a flame thrower, whose effective range is up to r2r_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 d2d_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 d3d_3 damage points. The fire will be quenched at the end of the (x+t2)(x+t_2)-th frame if was hit by a bunker at the xx-th frame. Moreover, if a burning invader was hit by a bunker again, supposing that it was hit at the yy-th frame, its burning time will be prolonged to the end of the (y+t2)(y+t_2)-th frame.

Now the round starts. There will be EE invaders in total, the ii-th of which will land at the starting point in the beginning of the ii-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 HP1HP_1.

A captain is much more powerful whose initial health point is HP2HP_2, with some level defdef of defense capability. Once attacked by a defense tower whose damage point is damagedamage, he will suffer from max⁡{1,damage−def}\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 TT frames of time.

Input Format

The test data contains several test cases and the first line in input contains an integer Tcase (Tcase≤10)Tcase~(Tcase\le 10) representing the number of test cases.

For every test case, The first line contains five integers n,k,L,En, k, L, E and TT 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≤TE\le T in all cases.

The following LL lines describe the path. The ii-th of them contains two integers xix_i and yiy_i describing the coordinate of the ii-th cell in the path. We guarantee that any two adjacent cells in the path share a common edge. The first cell locating at (x1,y1)(x_1,y_1) is the starting point and the last cell locating at (xL,yL)(x_L,y_L) is the destination where the village is.

The next line contains seven integers r1,d1,t1,r2,d2,t2r_1, d_1, t_1, r_2, d_2, t_2 and d3d_3 indicating all parameters about defense towers described as above. And then a line containing three integers HP1,HP2HP_1,HP_2 and defdef describes parameters about invaders.

The next kk lines describe all defense towers. The ii-th of them contains three integers typei,xitype_i, x_i and yiy_i where (xi,yi)(x_i,y_i) is the coordinate of the ii-th defense tower, and if typei=1type_i=1 the tower is a gun tower, or a bunker if typei=2type_i=2.

The last line contains a string of length EE, the ii-th digit in which describes the type of the ii-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 400400.

Output Format

For the ii-th test case, output Case #i: (without quotes) in the first line. Then output EE lines describing the final states of all invaders.

The ii-th line of them indicates the ii-th invader:

  • If it will invade the village successfully, output Arrive with Y HP(s). (without quotes) where Y represents his remaining HPHP.
  • If it will be killed in the tt-th frame, output Be killed in the t-th frame at (x,y). (without quotes), where (x,y)(x,y) describes the location of his final resting place.
  • If this invader will live up to the TT-th frame but not arrive at the village, output Be alive at (x,y) with Y HP(s). (without quotes), where (x,y)(x,y) represents his final coordinate in the TT-th frame and Y represents his remaining HPHP.
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).