BuffingPixie
2016 TCO Russia Regional · 2016-03-24 · by ffao
Problem Statement
You are playing a turn-based role-playing game. At the moment you are preparing a strategy that will defeat an enemy character in the fewest turns possible. At the beginning of the fight the enemy has HP hitpoints. The enemy dies when their hitpoints become zero or negative.
A less experienced player may simply try attacking each turn, but you know the importance of support skills. In each of your turns you may choose one of the following two actions: either Focus or Attack.
- Focus changes the amount of damage dealt by an Attack performed during your next turn.
- Attack deals some damage to the opponent. If you used Focus during your immediately previous turn, the attack decreases the enemy's hitpoints by buffedAttack. Otherwise, the attack decreases the enemy's hitpoints by normalAttack.
You are given the
Constraints
- HP will be between 1 and 10^9, inclusive.
- normalAttack will be between 1 and 10^9, inclusive.
- buffedAttack will be between 1 and 10^9, inclusive.
5 1 3 Returns: 4
One optimal strategy looks as follows: Turn 1: Focus. Turn 2: Attack. Our enemy's hitpoints decrease from 5 to 2. Turn 3: Focus. Turn 4: Attack. Our enemy's hitpoints decrease from 2 to -1.
10 20 50 Returns: 1
You can win by simply attacking on the first turn.
24 2 5 Returns: 10
497 40 45 Returns: 13
8400 1 5 Returns: 3360
10 2 1 Returns: 5
Note that buffedAttack does not have to be greater than normalAttack.
Submissions are judged against all 37 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BuffingPixie with a public method int fastestVictory(int HP, int normalAttack, int buffedAttack) · 37 test cases · 2 s / 256 MB per case