Problem N
Free the End
Having entered the end dimension together, our heroes now aim to free it from the tyrannical rule of its resident dragon. Alex has volunteered to scale the many obsidian towers to disable the end crystals, while Kai will keep the endermen out of the way. This leaves Steve to actually fight the dragon.
Steve has his diamond sword and a collection of instant health II potions that he prepared for the fight. Steve can use his sword to deal 4 damage to the dragon, but after each time he uses it, its durability will decrease by 1. If its durability ever gets to 0, his sword will break! Also, Steve starts with 20 health, and he can use one of the potions to instantly regain 8 health (but he cannot go above 20 health).
Due to the dragon’s size and low dexterity, Steve can take four turns before every action that the dragon takes. On each of Steve’s turns he can choose to either attack or drink a potion, while on each of the dragon’s turns it will attack Steve and deal 10 damage to him (reducing his health by 10).
Steve wants to know if he is adequately prepared to fight the dragon on his own (or whether he will need help from his friends)! Steve will win if he can reduce the dragon to zero health, while the dragon will win if it reduces Steve to zero health. Steve is confident that he can win with enough resources, but he is not sure whether his sword or potions will last through the fight.
Assuming that Steve plays optimally (to minimize the health of the dragon before calling for help), identify the following outcomes to the fight:
-
’Steve wins’ - Steve can successfully defeat the dragon on his own.
-
’broken sword’ - Steve’s sword will break before he can defeat the dragon.
-
’not enough potions’ - The dragon can reduce Steve’s health to zero.
In the case that both his sword will break and that he does not have enough potions, Steve wants to know which will happen first in the fight, as that is the point that he will need his friends to help him.
Input
The input consists of three integers, $s$, $d$, and $p$, respectively the durability of Steve’s sword, the dragon’s initial health, and the number of potions that Steve has.
You are given $1 \le s \le 2000$, $1 \le d \le 8000$, and $0 \le p \le 1000$.
Output
Output the outcome of the fight from the list above.
Explanation for Sample Input 1
In this input, Steve has no potions so all of his moves will be to attack. The fight will look like this
Attack, Attack, Attack, Attack (sword breaks)
Note that Steve also does not have enough potions, but his sword broke first.
Explanation for Sample Input 2
Steve now has a more durable sword, so it won’t break as soon. The fight will now look like this.
Attack, Attack, Attack, Attack, Dragon Attacks, Attack, Attack, Attack, Attack, Dragon Attacks (Steve’s health is now 0)
Note that Steve’s sword will still break after the next attack, but the dragon reduced his health to zero first.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 39 0 |
broken sword |
| Sample Input 2 | Sample Output 2 |
|---|---|
9 39 0 |
not enough potions |
| Sample Input 3 | Sample Output 3 |
|---|---|
9 39 1 |
broken sword |
| Sample Input 4 | Sample Output 4 |
|---|---|
10 39 1 |
Steve wins |
| Sample Input 5 | Sample Output 5 |
|---|---|
20 80 5 |
Steve wins |