FightMonsterDiv1 | Topcoder Archive

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

1000000000000

Returns: 1

```
1338
```
```
100
```
```
1
```
```
2
```
```
Returns: 6
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.