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.
Definition
- Class:
- FightMonsterDiv1
- Method:
- fightTime
- Parameters:
- long, long, int, long
- Returns:
- long
- Method signature:
- long fightTime(long hp, long attack, int level, long duration)
- (be sure your method is public)
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.
Examples
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
1
100
0
1
Returns: 1
980
100
10
1
Returns: 5
999999820408
3100
52
220
Returns: 34357
999999251054
7800
22
330
Returns: 32849
999999658720
900
89
724
Returns: 47178
999999679845
100
1
111
Returns: 1413671
999999854666
9700
39
792
Returns: 20096
999999492398
4300
59
641
Returns: 25660
999999594215
1000
52
649
Returns: 59489
999999575932
9600
50
642
Returns: 18045
999999370913
2500
27
37
Returns: 54284
999999051631
9000
43
344
Returns: 21409
999999917775
400
41
1000000000000
Returns: 49386
999999563945
2600
41
1000000000000
Returns: 19371
1338
100
1
2
Returns: 6
912137346518
100
1
1337
Returns: 1345224
997998999996
200
3
131
Returns: 576217
888888888888
999999900
1
1
Returns: 331
1000000000000
100
1
35
Returns: 1413976
5000
100
100
4
Returns: 5
1000000000000
100
1
1234
Returns: 1409190
10000001
10000000
0
1000000000000
Returns: 2
509627681598
50520063800
82
416600171536
Returns: 3
10000000000
100
100
1
Returns: 14139
1000000000000
999999999900
1
1000000000000
Returns: 2
1000000000000
3000
15
12
Returns: 66614
1000000000000
100
100
1
Returns: 141418
1
100
0
100000
Returns: 1
101
100
0
1
Returns: 2
201
100
0
1
Returns: 2
501
100
0
100
Returns: 3
2500
100
100
100
Returns: 4
61750
200
11
10000
Returns: 27
2000
100
0
1000
Returns: 5
1000000000000
1000
100
1
Returns: 44718
1000000000000
100
1
100
Returns: 1413716
2000
200
5
1
Returns: 6
1000000000000
1000000
67
5000000000
Returns: 773