FightMonsterDiv1
TCO19 SRM 749 · 2019-01-09 · by Blue.Mary
Problem Statement
Hero is fighting against a monster. The monster has hp hit points. This means that the monster will die when Hero deals it a total of hp damage or more.
Hero's basic attack deals attack points of damage. He has two things that can help him defeat the monster: a special passive skill and a magic scroll.
Hero has level skill points in the skill. The skill gradually increases the amount of damage he deals when attacking the monster multiple times. More precisely, each attack after the first one will deal M more points of damage than the previous one, where M = (level percent of attack).
The magic scroll can only be used once. The scroll activates a spell that will affect the next duration attacks. During each of these attacks Hero deals not just regular damage (calculated as explained above) but also magical damage. The amount of magical damage is always exactly four times the amount of regular damage.
One attack takes one second. Activating the scroll also takes one second (and during that second Hero cannot attack). Return the smallest number of seconds needed to kill the monster.
Constraints
- hp will be between 1 and 1012, inclusive.
- attack will be between 100 and 1012, inclusive.
- attack will be a multiple of 100.
- level will be between 0 and 100, inclusive.
- duration will be between 1 and 1012, inclusive.
201 100 10 10 Returns: 2
Hero can just attack. The first attack will deal 100 damage, the second one will deal 110 damage, and the monster will be defeated. Alternately, Hero can read the scroll and then deal 100 regular + 400 magical = 500 damage in a single attack.
74900 100 0 2 Returns: 742
Here is one optimal solution: Attack the monster 9 times, each time dealing 100 damage. (Total: 9 seconds, 900 damage.) Read the scroll. (Total: 10 seconds, 900 damage.) Attack the monster twice with the bonus from the spell, each time dealing 500 damage. (Total: 12 seconds, 1900 damage.) Attack the monster another 730 times, each time only dealing 100 damage again. (Total: 742 seconds, 74900 damage.)
1000000000000 1000000000000 100 1000000000000 Returns: 1
1000000000000 100 0 1 Returns: 9999999997
1000000000000 100 1 1 Returns: 1414112
Submissions are judged against all 43 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FightMonsterDiv1 with a public method long long fightTime(long long hp, long long attack, int level, long long duration) · 43 test cases · 2 s / 256 MB per case