Connection Status:
Competition Arena > EnemyTowers
SRM 450 · 2009-10-17 · by Rydberg · Search, Simulation
Class Name: EnemyTowers
Return Type: int
Method Name: attack
Arg Types: (int, int, int, int, int)
Problem Statement

Problem Statement

As a serious strategy-games player, you often need to find the best strategy for destroying your opponents' guard towers. You are currently preparing to play a game where your opponent has numWodT wooden towers and numStoT stone towers. Each tower has hpT hit points, and once a tower loses all its hit points, it is destroyed. You have myUnits soldiers. Because different weapons are required to destroy different types of towers, you must divide your soldiers into two groups. The first group will attack only wooden towers and the second group will attack only stone towers. You can divide your soldiers up however you like, but once the game begins, you are not allowed to re-assign them to different groups.

In each round of attacks, the following happens:
1. Each soldier from the first group attacks a single wooden tower and inflicts 1 hit point of damage. You can pick the tower independently for each soldier.
2. Each solider from the second group attacks a single stone tower and inflicts 1 hit point of damage. You can pick the tower independently for each soldier.
3. Your opponent attacks. The wooden towers will kill w*attackT of your soldiers from the first group, where w is the number of remaining wooden towers, and the stone towers will kill s*attackT of your soldiers from the second group, where s is the number of remaining stone towers.

Return the minimum number of rounds required to destroy all the towers, or return -1 if it is impossible.

Notes

  • More than one soldier can attack the same tower.

Constraints

  • myUnits will be between 1 and 1000000000, inclusive.
  • hpT, attackT, numWodT, numStoT will be each between 1 and 40000, inclusive.
Examples
0)
7
2
1
2
3
Returns: 2

Put 3 soldiers in the first group and 4 soldiers in the second group. Round 1: First group: Your soldiers destroy one wooden tower and leave the second tower with 1 hit point. Second group: Your soldiers destroy two stone towers. The one remaining wooden tower kills one of your soldiers in the first group, and the one remaining stone tower kills one of your soldiers in the second group. Round 2: First group: You have 2 soldiers remaining in the first group, and that's more than enough to destroy the last wooden tower. Second group: You have 3 soldiers remaining in the second group, and that's also more than enough to destroy the last stone tower.

1)
120
10
40000
6
6
Returns: 1

Towers are really powerful but luckily you have exactly enough soldiers to destroy them before they attack.

2)
119
10
40000
6
6
Returns: -1
3)
200
50
3
10
5
Returns: 6

Put 126 soldiers in the first group and 74 soldiers in the second group.

4)
1000000000
40000
5681
40000
40000
Returns: 15

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

Coding Area

Language: C++17 · define a public class EnemyTowers with a public method int attack(int myUnits, int hpT, int attackT, int numWodT, int numStoT) · 162 test cases · 2 s / 256 MB per case

Submitting as anonymous