1381 - EnemyTowers
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 120
Solved: 26
- Description
- 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. - Input
- Five integers: myUnits, hpT, attackT, numWodT, numStoT
- myUnits will be between 1 and 1000000000, inclusive.
- hpT, attackT, numWodT, numStoT will be each between 1 and 40000, inclusive.
- Output
- the minimum number of rounds required to destroy all the towers, or -1 if it is impossible.
- sample input
-
7 2 1 2 3 120 10 40000 6 6 119 10 40000 6 6 200 50 3 10 5
- sample output
-
2 1 -1 6
- hint
- - More than one soldier can attack the same tower. For the first test case: 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.
- source