ZOJ Problem Set - 3577
Consider that there are two kinds of units named Marine and Medic. Each marine has a gun which can create d damage per unit time. And each marine has a health point hp. The medic cannot export any damage, but each medic can heal h health point of the marines per unit time. And her energy is limited. One point of medics' energy can heal one point health point of the marines'. The medics are very clever. If there are m medics, you can consider them as one medic which has m times of healing speed and m times of energy. When a marine is under attack, we consider that the healing and attacking happen at the same time. Any marine's health point cannot exceed hp. Because of the limitation of the supply, the size of your army is limited. You can only create an army containing no more than n people. Of course you will get some enemies, and they will export a damage per unit time to your units. Your enemies will focus on one target each time, which means they will not attack the second marine until the first marine has been killed. After the first one killed, the next one will suffer the rest damage, then the third one. And they will only focus on the units which can export damage, which means that they will not attack the medics. Your enemies have enough reinforcement. So we consider that the damage from the enemies is a certain number a, which will not decrease under your attack.
For example, you have two marines with 5 hp and 4 damage per second, the enemy damage is 10 per second, the total healing speed is 3 per second, like 2 medic with 1.5 healing speed. The damage and healing happen the same time. Actually, we suffer 7 damage per second. After 5 / 7 second, we will lost the first marine. After a second, the total damage will be 5 / 7 * 8 + 2 / 7 * 4. But actually, we do not calculate the damage second by second.
So there comes the problem. As a commander, you should train how many marines and medics in your army to create the most powerful damage under the attack of your enemies.
There are several test cases.
For each test cases, you should print one line contains one integer, the number of the marine(s) in your army.
2 5 19 50 200 20 100 6 2 40 250 20
For the first sample, the best way is to train one marine and one medic.
When the medic has energy, the actual damage is 1.
After 200 / 19 seconds, the medic is out of energy, the marine's hp left is 50 - 1 * 200 / 19.
Then the damage becomes 20.
After (50 - 1 * 200 / 19) / 20 seconds more, the marine dies.
So the total damage will be ((200 / 19 + (50 - 1 * 200 / 19) / 20) * 5).
Author: LI, Tierui
Contest: ZOJ Monthly, February 2012