Towers
SRM 418 · 2008-09-20 · by Rydberg
SRM 418 · 2008-09-20 · by Rydberg · Simulation
Problem Statement
Problem Statement
As a serious strategy-games player, you decided to solve one of the most common problems - attacking your
opponent's guard towers.
Before the attack, you've got myUnits soldiers. Each soldier in a single round inflicts 1 hit point of damage to one of the towers.
Your opponent doesn't have any soldiers. However, he's got numT towers with hpT hit points each. Each tower kills attackT of your soldiers per round.
The course of one round:
1. Each soldier in your army attacks a tower of your choice for 1 hit point of damage. When a tower loses all its hit points, it is destroyed. You can pick the tower independently for each soldier.
2. Your opponent attacks. He will kill k*attackT of your soliders, where k is the number of remaining towers.
Your task is to destroy all the towers. If it is possible, return the minimum number of rounds you need to do this. Otherwise return -1.
Before the attack, you've got myUnits soldiers. Each soldier in a single round inflicts 1 hit point of damage to one of the towers.
Your opponent doesn't have any soldiers. However, he's got numT towers with hpT hit points each. Each tower kills attackT of your soldiers per round.
The course of one round:
1. Each soldier in your army attacks a tower of your choice for 1 hit point of damage. When a tower loses all its hit points, it is destroyed. You can pick the tower independently for each soldier.
2. Your opponent attacks. He will kill k*attackT of your soliders, where k is the number of remaining towers.
Your task is to destroy all the towers. If it is possible, return the minimum number of rounds you need to do this. Otherwise return -1.
Notes
- More than one soldier can attack the same tower in the same round.
Constraints
- myUnits will be between 1 and 1000000, inclusive.
- hpT, attackT, numT will each be between 1 and 10000, inclusive.
Examples
0)
13 2 3 8 Returns: 2
Round 1: - Your soldiers destroy 6 towers leaving one tower with 1 hit point and one tower with 2 hit points. - Your opponent attacks and kills 2*3=6 of your soldiers. Round 2: - You have 7 soldiers remaining, which is more than enough to take out the 3 hit points of the remaining towers.
1)
10 6 8 2 Returns: 2
2)
10 6 9 2 Returns: -1
3)
1 1 1 1 Returns: 1
4)
10000 10 2 2789 Returns: 10
Submissions are judged against all 114 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Towers with a public method int attack(int myUnits, int hpT, int attackT, int numT) · 114 test cases · 2 s / 256 MB per case