Problem F
Fight to Survive
You are the head of a group of survivors in the zombie apocalypse.
Just recently you’ve heard word of an incoming zombie horde heading to your facility. As commander in chief the responsibility falls on to you to prepare for the incoming invasion.
Luckily these zombies are very slow, allowing you and your
team to easily pick them off one by one. Every zombie has a
finite amount of health,
You and your team have devised the following strategy for dealing with the horde. The healthiest survivor will attack the closest zombie. In order to reduce the angle of attack, you and your team have created a funnel that allows the zombies to approach in single file.
There may be better strategies, but this was the one you and your team have chosen and failure to comply will result in a mutiny.
Strategy
Over the course of the stand-off two possible events can happen:
-
A zombie approaches the shelter, and stands in line outside of the funnel.
-
The next zombie is attacked by the healthiest survivor.
During the battle between a zombie and a survivor, the
survivor’s health is reduced by the health of the attacking
zombie and vice versa. If the zombie is too strong then the
survivor’s health is completely reduced and the zombie’s health
is reduced by the survivor’s lost health. An additional
survivor will be required to save them, in which case the same
process will repeat until either no survivors remain or the
zombie is eliminated (it is possible for a single sufficiently
powerful zombie to destroy your whole team). If the survivor
and zombie have the same amount of health then the zombie will
be killed and the survivor’s health will be reduced to
Once a survivor has had their health completely reduced they are put into the medical ward where they await treatment. Otherwise if they survive a zombie attack event they’ll take a break to recuperate, making them unavailable for the next event afterwards.
If a survivor returns to base and they have the same health as another survivor, then the survivor with the highest maximum, or original health, goes first.
As the team’s only doctor, you do not participate in the
battle. Instead, starting at the beginning of the battle, at
the beginning of every
Using the strategy outlined above, can your team survive the zombie onslaught or do you eventually get overrun?
Input
Input begins with two space-separated integers indicating
the number of survivors
The next line contains
It is guaranteed that there will be an ATTACK command only if there are zombies to attack, and that the number of ATTACK commands equals the number of APPROACH commands.
Output
Output is a single line containing either the string success, if your team is able to withstand the zombies, or overrun if there are no survivors available to attack the next zombie. Note that even if all survivors are in the medical ward at the end, you have still withstood the zombies because the doctor is still alive.
Explanation of Sample 1
A single survivor is waiting with
You are overrun.
Explanation of Sample 4
You have three survivors with healths
In the first event, a supercharged zombie with
In the third event, a second zombie with
A third zombie with
In the seventh event, the final menacing zombie with
The second survivor, now with
With no more zombies in sight, you tend to the exhausted survivors and write down a single word summing up the terrifying day as you stare into the sunset—success!
Sample Input 1 | Sample Output 1 |
---|---|
1 2 100 4 APPROACH 12 APPROACH 13 ATTACK ATTACK |
overrun |
Sample Input 2 | Sample Output 2 |
---|---|
2 2 100 100 4 APPROACH 12 APPROACH 13 ATTACK ATTACK |
success |
Sample Input 3 | Sample Output 3 |
---|---|
5 3 20 30 12 15 9 12 APPROACH 20 APPROACH 25 ATTACK APPROACH 15 APPROACH 26 ATTACK APPROACH 38 APPROACH 14 ATTACK ATTACK ATTACK ATTACK |
overrun |
Sample Input 4 | Sample Output 4 |
---|---|
3 8 100 27 23 8 APPROACH 100 ATTACK APPROACH 12 ATTACK APPROACH 13 ATTACK APPROACH 75 ATTACK |
success |