EnemyTowers
SRM 450 · 2009-10-17 · by Rydberg
Problem Statement
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.
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.
120 10 40000 6 6 Returns: 1
Towers are really powerful but luckily you have exactly enough soldiers to destroy them before they attack.
119 10 40000 6 6 Returns: -1
200 50 3 10 5 Returns: 6
Put 126 soldiers in the first group and 74 soldiers in the second group.
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.
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