Barracks

SRM 418 · 2008-09-20 · by Rydberg

SRM 418 · 2008-09-20 · by Rydberg · Math, Simple Search, Iteration, Simulation

Show categories

Class Name: Barracks

Return Type: int

Method Name: attack

Arg Types: (int, int, int)

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.

Constraints

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

Examples

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
2
1
Returns: -1

1
1
1
Returns: 1

25
200
10
Returns: 13

400
400
400
Returns: 1

Submissions are judged against all 236 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Barracks with a public method int attack(int myUnits, int barHp, int unitsPerRound) · 236 test cases · 2 s / 256 MB per case