P2586 [ZJOI2008] Kill Ants

Recently, Jiajia got hooked on a fun mini-game: antbuster. The rules are simple: on a map, the top-left corner is the ant nest, and the bottom-right corner is the cake. Ants continuously crawl out of the nest, trying to carry the cake back to the nest. Your task is to use the initial funds and the bounty from killing ants to build defense towers to kill those ants that try to grab your cake. To get the highest possible score, Jiajia designed many tower layouts. But after trying only a small fraction of them, Jiajia found the game too time-consuming. To save time, Jiajia decided to write a program to simulate each plan and evaluate it based on the results. Based on experience in the game and some parameters found online, Jiajia guessed the ants’ crawling algorithm and assumes the ants in the game choose their routes according to the following rules: 1. At the start of each second, every ant is on some grid point in the plane. If an ant is not carrying the cake, it leaves $2$ units of pheromone at that point; otherwise, it leaves $5$ units. Then it chooses one direction among north, south, east, and west to crawl to. 2. The direction selection rule is: first, the destination point reached after moving one unit must not be occupied by another ant or a tower, and that point cannot be the ant’s position from the previous second (unless the ant was stuck in the previous tick and still cannot move now). Of course, ants will not crawl outside the map (we define such points as unreachable). If there are multiple choices, the ant will choose the point with the highest pheromone. 3. If there is still a tie, the ant first faces due east. If east is not among the selectable directions, it turns $90^\degree$ clockwise and checks again; if still not, it continues turning $90^\degree$ clockwise until it finds a valid direction. 4. If we regard the time when each ant appears at the nest entrance as the first second of its life, then whenever the ant’s age in seconds is a multiple of $5$, it first determines a direction according to rules 1–3, then turns $90^\degree$ counterclockwise from that facing. If moving along the current direction leads to an unreachable point, it keeps turning $90^\degree$ counterclockwise each time until it faces a reachable point. The direction determined in this way is the final direction the ant will crawl. 5. If all four neighboring points are unreachable, the ant will choose to stay at its current point for this second. When determining the movement direction next second, its previous position is its current resting point. 6. You may assume that after choosing a direction, the ant instantly moves to its target point and then remains at the target point for the rest of the second. 7. Ants move in their birth order. Earlier-born ants move first. Next, some information about the map: 1. Each second, the pheromone value on every map point decreases by $1$ unit if it is positive. 2. Some places on the map are towers. Tower coordinates are given in the input. 3. The map’s length and width are given in the input. For an $n \times m$ map, the top-left corner is $(0,0)$ and the bottom-right corner is $(n,m)$. The ant nest is at $(0,0)$ and the cake is at $(n,m)$. 4. You can consider an ant as a circle of diameter $1$, with its center located at the grid point where the ant is. 5. At the beginning of the game, there are no ants on the map, and the pheromone value at every point is $0$. Some information about towers: 1. Towers are placed at grid points on the map. 2. For simplicity, we assume all towers are laser towers. A laser tower fires once per second, deals $d$ damage per shot, and has attack range $r$. You may assume that towers only begin attacking after all ants have finished moving in that second. Moreover, a tower can hit an ant only if the distance from the tower to the center of the ant’s circle does not exceed $r$. 3. If an ant is carrying the cake, it becomes the target. That is, any tower that can reach it will aim at it. If the cake remains at its original position, each tower will choose the nearest ant to attack; if there is a tie, it picks the earlier-born one. If there is a cake-carrying ant but it is outside a certain tower’s range, that tower chooses the nearest ant to attack. 4. Laser towers have a peculiar property: once a target is selected, as long as the target is within range, all ants whose circles intersect the line segment from the tower to the target ant’s center (here, being “hit” is determined by whether the laser segment and the ant’s circle have an intersection) will be hit and lose $d$ HP. However, the laser will not penetrate through its target to hit ants behind it. 5. Although towers can be upgraded in the actual game, here we assume the tower layout and levels are fixed and will not change. Now about the ant nest: 1. If there are fewer than $6$ ants on the map and the nest entrance (i.e., point $(0,0)$) is unoccupied, one ant will crawl out each second until there are $6$ ants on the map. 2. A newly born ant stands at the nest entrance. 3. Each ant has a level, which determines its HP. An ant of level $k$ has HP $\lfloor 4 \times 1.1^k \rfloor$ (where $\lfloor x \rfloor$ denotes the floor of $x$). Each time it is hit by a tower, its HP decreases by $d$. Note that an ant with HP equal to $0$ can still move around vigorously; only when an ant’s HP becomes negative is it considered dead. 4. Ant levels are assigned as follows: the first $6$ ants are level $1$, ants $7 \sim 12$ are level $2$, and so on. Ants numbered $6k+1 \sim 6k+6$ have level $k+1$ ($k \in \Bbb{N}$). Finally, an introduction to the cake: 1. For simplicity, assume there is only the last piece of cake left. If an ant reaches the cake’s position while the cake is not being carried, that ant picks up the cake. When an ant is killed, the cake returns to $(n,m)$. 2. If an ant carrying the cake reaches the nest location, we consider the ant to have successfully stolen the cake, and the game ends. This tick does not contribute to the ant’s age. 3. When an ant picks up the cake, its HP increases by $\left\lfloor \dfrac{x}{2} \right\rfloor$ (where $x$ is the ant’s HP at birth), but does not exceed its maximum HP. To sum up, what happens within one second: 1. At the very beginning of the second, if there are fewer than $6$ ants on the map, one ant is born at the nest entrance. 2. Then ants leave pheromones at their current points and decide their moves. Earlier-born ants move first. 3. After movement, if an ant is at the cake’s position and the cake has not been taken, it picks up the cake, gains HP, and is set as the target by all towers at this moment. 4. Then all towers attack simultaneously. If the ant carrying the cake dies after the attack, the cake instantly returns to its place. After the cake-carrying ant dies, the cake will reappear only after all ants have finished moving in the next second. Only ants that appear at $(n,m)$ in the next second can pick up the cake. 5. After the attack, if the cake-carrying ant is alive and at the nest’s position, we consider the cake stolen and the game ends at this moment. 6. Finally, the pheromone value on every map point decreases by $1$ unit. All ants’ ages increase by $1$. The long second ends here.

The first line contains two positive integers $n, m$, the map’s length and width, separated by a space. The second line contains three integers $s, d, r$, denoting the number of towers, the damage per attack, and the attack range, respectively. The next $s$ lines each contain two integers $x, y$, describing the position of a tower. Of course, there are no towers at the nest entrance or at the cake’s position. The last line contains a positive integer $t$, indicating that we simulate the first $t$ seconds of the game.

If the cake is stolen by second $t$ or earlier, output a line `Game over after x seconds`, where $x$ is the time when the game ends; otherwise, output `The game is going on`. If the game ends by second $t$ or earlier, output the information of all ants at the end of the game; otherwise, output the information of all ants after $t$ seconds. The format is as follows: The first line is an integer $s$, the total number of ants alive at that time. The next $s$ lines each contain five integers, representing an ant’s age (in seconds), level, current HP, and its position $(a,b)$ on the map, in that order. Output should be sorted by age in descending order.

Sample explanation: On a $3 \times 5$ map, there is one laser tower with damage $1$ and attack range $2$, located at $(2,2)$. Simulate the first $5$ seconds of the game. Within $5$ seconds, $5$ ants are born. They all crawl east. Among them, ants $1 \sim 4$ are each hit for $1$ HP when passing through $(0,2)$ by the laser tower. In the $5$-th second, the earliest-born ant would have moved east according to movement rules 1–3, but due to rule 4, after finding that moving north or west would lead to unreachable points, it finally chooses to move south. Constraints: For $100\%$ of the testdata, $1 \leqslant n,m \leqslant 8$, $s \leqslant 20$, $t \leqslant 2 \times 10^5$, $0 \leqslant d \leqslant 10^4$, $0 \leqslant r \leqslant 15$. (Here $s$ denotes the total number of towers.) Translated by ChatGPT 5