Statistics

Problem Statement for "Mutalisk"

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.

Definition

Class:
Mutalisk
Method:
minimalAttacks
Parameters:
int[]
Returns:
int
Method signature:
int minimalAttacks(int[] x)
(be sure your method is public)

Constraints

  • x will contain between 1 and 20 elements, inclusive.
  • Each element in x will be between 1 and 60, inclusive.

Examples

  1. {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}.

  2. {54,18,6}

    Returns: 6

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

  3. {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.

  4. {55,60,53}

    Returns: 13

  5. {60}

    Returns: 7

  6. {44,60,29,24,31,17,39,10,55,2,13,45,12,23,11,13}

    Returns: 33

  7. {40,50,7}

    Returns: 8

  8. {58,37,30,3,23,51,27,37,16,22,56,29,37,35,58,44}

    Returns: 44

  9. {31,14}

    Returns: 5

  10. {36,54,33,26,37,46,6}

    Returns: 19

  11. {24,51,36,7,41,24,11,22,13,56,52,58,16,54}

    Returns: 36

  12. {39,2,17,8,56,36,60,43,42,11,14,28}

    Returns: 28

  13. {10,57,19,22,45,48,21,29,8,49,18,51,48,31,23,4,20}

    Returns: 39

  14. {44,35,12,59,47,14,31,6,22}

    Returns: 21

  15. {9,35,33,24}

    Returns: 8

  16. {22,24,27,5,37,59,17,16,18,59,48,26,60,32,22}

    Returns: 37

  17. {47,31,16,14,25,15,58,15,45,42,5}

    Returns: 25

  18. {50}

    Returns: 6

  19. {55,54,51,4,46,34,41,14,23,58,36,17,60}

    Returns: 38

  20. {35,28}

    Returns: 6

  21. {29,59,6,30,59,23,23,9,40,37,36,6}

    Returns: 28

  22. {46,31,50}

    Returns: 10

  23. {50,59,26,55,38,33,8,4,51}

    Returns: 25

  24. {12,4,56,43}

    Returns: 9

  25. {10,59,52,10,57,16,39,41,10,1,35,34,23,49}

    Returns: 34

  26. {54,26,47,10,31,3,14,41,51,24,19,18}

    Returns: 26

  27. {12,2,56}

    Returns: 7

  28. {42,37,54,39,3,33,4,5,33,34,48,26,17,41,56,6,51}

    Returns: 41

  29. {9,2,4,46,38,36,17,48,36,45,30,14,32,8,29,2}

    Returns: 31

  30. {17,57,10,22,14,33,8,3,33,57,19,26}

    Returns: 23

  31. {35,23,11,46,5,50,7,12,26,13}

    Returns: 18

  32. {42,6,13,10,8,4,22,5,13}

    Returns: 10

  33. {23,32,50,18,51,11,27,3,59,19,34}

    Returns: 26

  34. {42,5,3,58,21}

    Returns: 10

  35. {26,9,3,11,43,21,48,39}

    Returns: 16

  36. {53,16,57,29,29,31,19,40,20,7,25,28,7,17,18,31,55,35,50}

    Returns: 44

  37. {19,21,42,42,45,54,26,39,17,22,31,51,33}

    Returns: 34

  38. {21,44,11,40,58,60,60,51,44,53,38,1,16,20,8,43,39,5}

    Returns: 48

  39. {16,49,32,18,46,27,10,43,18,49,52,37,30,33,27,17}

    Returns: 39

  40. {30,7,60,8,21,45,18,34,56,50,8,57,48,54,37,11,36,57,12,47}

    Returns: 54

  41. {37,48,35,22,24,7,45,40,16,19,8,3,8,46,26,23,48,13}

    Returns: 36

  42. {19,48,19,55,20,33,14,50,20,48,59,36,46,23,22,26,5}

    Returns: 42

  43. {25,11,7,10,1,52,44,47,12,29,11,51,37}

    Returns: 26

  44. {24,46,13,27,39,52,40,57,8,6,51,10,36,25}

    Returns: 34

  45. {23,54,47,37,28,1,21,51,51,58,57}

    Returns: 33

  46. {17,9,5,40,25,12,60,18}

    Returns: 15

  47. {6,10}

    Returns: 2

  48. {3,17,18,32,41,23,33,25,2,3,16,33,51}

    Returns: 23

  49. {26,2,27}

    Returns: 5

  50. {49,32,5,36,10,20,18,51}

    Returns: 17

  51. {42,56,5,36,26,18,19,36,18,29,8,29,22,42,34}

    Returns: 33

  52. {16,26,13,12,56,34,31,59,6,50,4,47,35,40}

    Returns: 33

  53. {30,42,29,3,20,60,60,29}

    Returns: 21

  54. {14,42,38,48,29,41,39,36,37,59,34,59,59,57,38,16}

    Returns: 50

  55. {21,11,11,20,32,20,22,20,4,41,9,45,50}

    Returns: 24

  56. {1,20,29,24,22,60,48,9,41,28,6,11,22,23,51,55,40,18,29,59}

    Returns: 46

  57. {11,52,58,11,40,4,10,1,21,47,50,4,33,54,44,52,55,5,27,43}

    Returns: 48

  58. {1,30,11,21,2,25,37,20,21,20,8,12,7,33,36,60,14,32,33,33}

    Returns: 36

  59. {2,47,45,42,38,59,19,3,40,9,43,17,35,31,4,51,12,10,9,7}

    Returns: 41

  60. {60,49,2,30,18,6,50,43,43,39,59,45,56,48,14,6,17,30,9,27}

    Returns: 51

  61. {32,59,20,33,34,43,31,18,28,46,32,31,53,6,21,52,48,20,56,46}

    Returns: 55

  62. {34,57,8,42,53,26,23,37,44,48,16,58,50,8,28,9,45,6,56,18}

    Returns: 52

  63. {33,11,29,30,7,28,51,15,1,36,36,22,26,31,42,16,24,6,32,24}

    Returns: 39

  64. {13,48,11,20,50,46,6,58,18,19,42,54,30,45,59,38,1,47,20,42}

    Returns: 52

  65. {47,46,51,30,22,2,32,57,3,36,14,24,48,54,55,38,25,10,18,31}

    Returns: 50

  66. {57,54,53,50,56,52,60,56,58,60,50,51,60,51,54,50,57,52,51,56}

    Returns: 84

  67. {58,53,58,60,60,50,57,50,60,51,56,57,60,55,54,55,56,52,50,55}

    Returns: 86

  68. {58,59,59,50,57,56,56,51,52,53,50,53,50,54,54,57,60,59,51,56}

    Returns: 85

  69. {52,54,55,53,55,60,59,52,51,57,54,55,53,55,55,53,60,55,52,53}

    Returns: 85

  70. {51,53,50,56,54,51,50,50,51,60,50,57,55,55,55,53,53,59,57,53}

    Returns: 83

  71. {57,60,59,59,52,52,54,52,58,57,59,51,50,56,54,53,55,52,59,59}

    Returns: 86

  72. {50,52,50,51,52,53,52,60,52,59,51,50,55,55,56,56,58,60,57,55}

    Returns: 84

  73. {56,59,57,50,53,51,57,54,52,56,50,56,57,52,56,57,60,57,60,50}

    Returns: 85

  74. {55,56,50,60,53,51,53,56,52,57,60,52,54,51,60,56,58,57,57,53}

    Returns: 85

  75. {59,51,57,59,60,59,51,53,54,50,56,53,55,52,58,51,52,52,54,51}

    Returns: 84

  76. {56,58,50}

    Returns: 13

  77. {55,50,51}

    Returns: 13

  78. {52,53,50}

    Returns: 12

  79. {55,53,59}

    Returns: 13

  80. {52,59,52}

    Returns: 13

  81. {56,60,55}

    Returns: 14

  82. {52,51,50}

    Returns: 12

  83. {55,60,55}

    Returns: 14

  84. {58,52,51}

    Returns: 13

  85. {52,53,52}

    Returns: 13

  86. {19,34,56}

    Returns: 9

  87. {28,6,54}

    Returns: 8

  88. {33,57,23}

    Returns: 9

  89. {14,13,28}

    Returns: 5

  90. {49,20,7}

    Returns: 7

  91. {54,51,13}

    Returns: 10

  92. {54,27,27}

    Returns: 9

  93. {20,27,29}

    Returns: 6

  94. {44,30,60}

    Returns: 11

  95. {29,6,52}

    Returns: 8

  96. {60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60,60}

    Returns: 93

  97. {18, 42, 44, 33, 23, 7, 42, 44, 8, 23, 26, 48, 11, 58, 43, 15, 4, 29, 24, 52 }

    Returns: 46

  98. {9, 2, 2 }

    Returns: 2

  99. {45, 17, 3 }

    Returns: 6

  100. {3, 5, 18 }

    Returns: 3

  101. {30, 3 }

    Returns: 4

  102. {60, 1 }

    Returns: 7

  103. {7, 8, 9 }

    Returns: 3

  104. {60 }

    Returns: 7

  105. {47, 13, 10, 2, 3, 8, 51, 20, 24, 47, 1, 7, 53, 17, 12, 9 }

    Returns: 25

  106. {9, 14 }

    Returns: 3

  107. {1, 12 }

    Returns: 2

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: