TopCoder problem "BarracksEasy" used in SRM 418 (Division II Level Three)



Problem Statement

    As a serious strategy-games player, you decided to solve one of the most common problems - attacking your opponent's building (barracks), which constantly produces new soldiers.



Before the attack, you've got myUnits soldiers. In a single round, each soldier can either kill one of your opponent's soldiers or inflict 1 hit point of damage to the barracks.

Your opponent doesn't have any soldiers initially. However, his barracks has barHp hit points and produces unitsPerRound soldiers per round.



The course of one round:

1. Each solider from your army either kills one of your opponent's soldiers or inflicts 1 hit point of damage to the barracks. Each soldier can choose to do something different. When the barracks loses all of its hit points, it is destroyed.

2. Your opponent attacks. He will kill k of your soldiers, where k is the number of remaining soldiers he has.

3. If the barracks are not yet destroyed, your opponent will produce unitsPerRound new soldiers.



Your task is to destroy the barracks and kill all your opponent's soldiers. If it is possible, return the minimum number of rounds you need to do this. Otherwise return -1.
 

Definition

    
Class:BarracksEasy
Method:attack
Parameters:int, int, int
Returns:int
Method signature:int attack(int myUnits, int barHp, int unitsPerRound)
(be sure your method is public)
    
 

Constraints

-myUnits, barHp, unitsPerRound will each be between 1 and 50, inclusive.
 

Examples

0)
    
10
11
15
Returns: 4
Round 1:

- All your soldiers attack the barracks, leaving it with 1 hit point.

- Your opponent has no soldiers, so he cannot kill any of your soldiers.

- Your opponent's army increases from 0 soldiers to 15 soldiers.



Round 2:

- One of your soldiers destroys the barracks. The other nine kill 9 of your opponent's soldiers.

- Your opponent has 6 soldiers, so he kills 6 of your soldiers.

- The barracks have been destroyed, so no new soldiers are produced.



Round 3:

- You have got 4 soldiers, so you decrease your opponent's army to 2 soldiers.

- Your opponent kills 2 of your soldiers.

- The barracks have been destroyed, so no new soldiers are produced.



Round 4:

- You kill 2 remaining soldiers.

1)
    
3
10
4
Returns: -1
2)
    
2
10
1
Returns: 9
3)
    
11
12
9
Returns: 2

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10073

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13509&pm=10073

Writer:

Rydberg

Testers:

PabloGilberto , Olexiy , Mike Mirzayanov , ivan_metelsky , darnley

Problem categories:

Dynamic Programming, Greedy, Simulation