PROBLEM STATEMENT
A Zergling dies after 3 hits of a Zealot. A Zealot needs 32 Zergling hits to
die. Zerglings' attack rate is twice as fast as Zealots'. That is, while a
Zealot makes one hit, a Zergling makes two hits. Up to three Zealots can attack
a Zergling together at the same time. No more than 10 Zerglings can attack one
Zealot together at the same time.
Zealots attack first.
Your task is, given the number of Zealots (in full health) before the attack,
return the minimum number of Zerglings needed for Zerglings to win the battle.
In more detail:
- Recovery rate for everybody is zero. That means the health points aren't
gained back with time.
- Zealots attack first, each Zealot has one hit. Then Zerglings attack, each
Zergling has 2 hits. Then Zealots attack, and so on...
- Zealots distribute their attack in the following manner: they start from
attacking the weakest Zerglings (they want to minimize the number of Zerglings
in the next Zerglings' attack). If a Zergling needs one hit to die, then only
one Zealot attacks it, if a Zergling needs two hits to die, then two Zealots
(if they are available) attack it. A healthy Zergling needs three hits to die,
in this case, if three Zealots are available, they attack the Zergling and kill
it.
- Zerglings distribute their attack in the following manner: they start from
the weakest Zealots and use as many Zerglings as necessary to produce the
maximum number of hits on that turn. For example, if a Zealot needs 8 hits to
die, then 4 Zerglings attack him and kill him during their turn (if 4 Zerglings
are available). (As Zealots receive even number or hits for each Zerglings'
attack, we never have a Zealot with an odd number of health points).
EXAMPLE OF A BATTLE
Let us consider an attack of 5 Zealots in full health on 28 Zerglings in full
health. We may say that each Zealot has 32 health points and each hit removes
one point, and each Zergling has 3 health points.
First Round. The Zealots attack: three of the Zealots kill 1 Zergling and the
other two Zealots hit another Zergling, reducing his health points by 2. Now we
have 26 full health Zerglings left and 1 Zergling with 1 health point. Then the
Zerglings attack: ten of the Zerglings (maximum) attack the first Zealot with
20 hits altogether, ten of the other Zerglings attack the second Zealot, and
the last 7 Zerglings attack the third Zealot. Now we have 2 Zealots each with
12 health points left, 1 Zealot with 18 health points left and 2 Zealots in
full health.
Second Round. Now the Zealots attack again: 1 Zealot finishes the 1-health
point Zergling, 3 Zealots kill one more Zergling, and the fifth Zealot hits
another Zergling. So we have 1 Zergling with 2 health points and 24 full health
Zerglings. Then the Zerglings attack: 6 Zerglings finish the first Zealot,
another 6 Zerglings finish the second Zealot, another 9 Zerglings finish the
third zealot, and the last 4 Zerglings give 8 hits to one of the Zealots. Hence
we have 1 Zealot with 24 health points left and 1 Zealot in full health.
Third Round. The Zealots attack: there are only two of them, they finish the
weak Zergling, and we have 24 full health Zerglings left. After the Zerglings
attack again we have 1 Zealot with 4 health points and 1 with 12 health points.
Fourth Round. The Zealots attack, leaving one 1-point Zergling and 23 full
health Zerglings. Then the Zerglings attack finishing both Zealots. The
Zerglings win with 23 full health Zerglings and one 1-health point Zergling left.
This example of a battle shows that when input is 5, the answer is not more
than 28.
DEFINITION
Class: StarCraft
Method: battle
Parameters: int
Returns: int
Method signature (be sure your method is public): int battle(int zealots);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- zealots is between 1 and 1000 inclusive
EXAMPLES
1. zealots = 1, return 4
2. zealots = 2, return 6
3. zealots = 3, return 9
4. zealots = 100, return 259
5. zealots = 1000, return 2587