Connection Status:
Competition Arena > Mutalisk

Mutalisk

SRM 658 · 2015-05-01 · by cgy4ever

SRM 658 · 2015-05-01 · by cgy4ever · Dynamic Programming
Class Name: Mutalisk
Return Type: int
Method Name: minimalAttacks
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Fox Ciel is writing an AI for the game Starcraft and she needs your help.

In Starcraft, one of the available units is a mutalisk. Mutalisks are very useful for harassing Terran bases. Fox Ciel has one mutalisk. The enemy base contains one or more Space Construction Vehicles (SCVs). Each SCV has some amount of hit points.

When the mutalisk attacks, it can target up to three different SCVs.
  1. The first targeted SCV will lose 9 hit points.
  2. The second targeted SCV (if any) will lose 3 hit points.
  3. The third targeted SCV (if any) will lose 1 hit point.
If the hit points of a SCV drop to 0 or lower, the SCV is destroyed. Note that you may not target the same SCV twice in the same attack.

You are given a int[] x containing the current hit points of your enemy's SCVs. Return the smallest number of attacks in which you can destroy all these SCVs.

Constraints

  • x will contain between 1 and 20 elements, inclusive.
  • Each element in x will be between 1 and 60, inclusive.
Examples
0)
{12,10,4}
Returns: 2

You can destroy all SCVs in two attacks as follows: Target the SCVs in the order 0, 2, 1. Their hit points after the attack will be {12-9, 10-1, 4-3} = {3, 9, 1}. Target the SCVs in the order 1, 0, 2. Their hit points will drop exactly to {0, 0, 0}.

1)
{54,18,6}
Returns: 6

You should attack 6 times, always in the order 0, 1, 2.

2)
{1,1,1,1,1,1,1,1,1,1}
Returns: 4

There are 10 SCVs, each with just a single hit point. Your attack can kill only three of them, therefore at least 4 attacks are needed.

3)
{55,60,53}
Returns: 13
4)
{60}
Returns: 7

Submissions are judged against all 107 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Mutalisk with a public method int minimalAttacks(vector<int> x) · 107 test cases · 2 s / 256 MB per case

Submitting as anonymous