50 - ZOJ Monthly, February 2006 - 1007
Tower Defense(TD) is a kind of rpg game in the warcraft3, which is very popular. in this game, you can build some tower near the road, and the enemy come along the road. when the enemy in the tower's attack range, the tower can attack the enemy. and each attack the enemy's life will reduce as the damage of the tower. When the enemy's life less than or equals 0, it dies. The mission of TD is kill all the enemies.
Now let's consider an easy situation. In the X-Y reference frame, there are n towers, each has a coordinate (x,y), an attack range, an attack type. m enemies come from (0,0) to (-10,0), in a line, with the length 2, and the enemies are come one by one. For example, in time 0 the all m enemies in (0,0), then in time 1 the first enemy go to (-2,0), in time 2 the first enemy go to (-4,0), the second enemy go to (-2,0), and so on, when an enemy go to (d,0)(d<=-10), we failed, even if it is still poisoned at this time, or we succeed. when the eneny in (0,0) and (d,0)(d<=-10), the tower can not attack, even if the enemy is in the tower's attack range. To simplify the problem, at each time each tower can attack once. when more than one enemy in its range, we can control it to attack any one, or even control it not attack, with the best strategy.
There are three attack type:
The first line of the input is n, m,life and poison_damage, the number of the towers, the number of the enemies, the life of enemy and the poison damage of poison attack. n<6, m<6, life<1000, 0<poison_damage<1000. Next n lines is the description of each tower, the first 5 number is x, y, range, damage, attack_type, the attack_type can be 0, 1, 2, which denote common attack, poison attack, freezing attack. 0<damage<1000. All are integers. a line with n=m=life=0 denoted the end of input.
If we succeed in the tower defense, output "succeed", or output "fail", in a separate line.Sample Input:
1 1 10 5 1 1 20 10 0 1 1 20 5 -2 0 1 10 0 2 2 40 5 -3 0 1 30 0 -7 0 1 10 0 0 0 0 5Sample Output:
succeed fail succeed
Author: LAI Chunbo