Statistics

Problem Statement for "EnemyTowers"

Problem Statement

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.

Definition

Class:
EnemyTowers
Method:
attack
Parameters:
int, int, int, int, int
Returns:
int
Method signature:
int attack(int myUnits, int hpT, int attackT, int numWodT, int numStoT)
(be sure your method is public)

Notes

  • More than one soldier can attack the same tower.

Constraints

  • myUnits will be between 1 and 1000000000, inclusive.
  • hpT, attackT, numWodT, numStoT will be each between 1 and 40000, inclusive.

Examples

  1. 7

    2

    1

    2

    3

    Returns: 2

    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.

  2. 120

    10

    40000

    6

    6

    Returns: 1

    Towers are really powerful but luckily you have exactly enough soldiers to destroy them before they attack.

  3. 119

    10

    40000

    6

    6

    Returns: -1

  4. 200

    50

    3

    10

    5

    Returns: 6

    Put 126 soldiers in the first group and 74 soldiers in the second group.

  5. 1000000000

    40000

    5681

    40000

    40000

    Returns: 15

  6. 1000000000

    40000

    5682

    40000

    40000

    Returns: -1

  7. 1000000000

    40000

    40000

    40000

    40000

    Returns: -1

  8. 1000000000

    16405

    40000

    40000

    40000

    Returns: 5

  9. 1000000000

    16406

    40000

    40000

    40000

    Returns: -1

  10. 1000000000

    40000

    40000

    40000

    450

    Returns: -1

  11. 1000000000

    40000

    40000

    449

    40000

    Returns: 7

  12. 1000000000

    40000

    40000

    20226

    20224

    Returns: -1

  13. 1000000000

    40000

    40000

    20223

    20226

    Returns: 6

  14. 15960245

    40000

    1

    40000

    40000

    Returns: -1

  15. 15960246

    40000

    1

    40000

    40000

    Returns: 1648

  16. 2000000

    10000

    3

    10000

    10000

    Returns: -1

  17. 79999

    1

    40000

    40000

    40000

    Returns: -1

  18. 80000

    1

    40000

    40000

    40000

    Returns: 1

  19. 1

    1

    1

    1

    1

    Returns: -1

  20. 2

    1

    1

    1

    1

    Returns: 1

  21. 566

    40000

    1

    1

    1

    Returns: 265

  22. 565

    40000

    1

    1

    1

    Returns: -1

  23. 251082761

    6321

    39957

    7307

    37932

    Returns: -1

  24. 251082762

    6321

    39957

    7307

    37932

    Returns: 4

  25. 723344864

    31765

    21532

    38298

    2997

    Returns: -1

  26. 723344865

    31765

    21532

    38298

    2997

    Returns: 10

  27. 671716922

    23944

    26905

    39218

    4760

    Returns: -1

  28. 671716923

    23944

    26905

    39218

    4760

    Returns: 8

  29. 115935662

    3363

    19624

    29267

    10347

    Returns: -1

  30. 115935663

    3363

    19624

    29267

    10347

    Returns: 4

  31. 633551945

    38483

    21394

    3744

    28051

    Returns: -1

  32. 633551946

    38483

    21394

    3744

    28051

    Returns: 12

  33. 196215157

    17449

    13330

    5428

    14234

    Returns: -1

  34. 196215158

    17449

    13330

    5428

    14234

    Returns: 9

  35. 802412978

    33056

    20327

    22310

    23076

    Returns: -1

  36. 802412979

    33056

    20327

    22310

    23076

    Returns: 9

  37. 801950219

    29442

    18748

    14607

    35762

    Returns: -1

  38. 801950220

    29442

    18748

    14607

    35762

    Returns: 9

  39. 423357568

    18704

    18265

    30045

    6820

    Returns: -1

  40. 423357569

    18704

    18265

    30045

    6820

    Returns: 8

  41. 716286293

    39797

    24694

    9816

    23740

    Returns: -1

  42. 716286294

    39797

    24694

    9816

    23740

    Returns: 10

  43. 9918873

    12094

    4

    8494

    37014

    Returns: -1

  44. 9918874

    12094

    4

    8494

    37014

    Returns: 534

  45. 8851541

    18779

    10

    16183

    4479

    Returns: -1

  46. 8851542

    18779

    10

    16183

    4479

    Returns: 372

  47. 10331734

    20454

    6

    10006

    19739

    Returns: -1

  48. 10331735

    20454

    6

    10006

    19739

    Returns: 526

  49. 33998805

    33147

    8

    27098

    39439

    Returns: -1

  50. 33998806

    33147

    8

    27098

    39439

    Returns: 592

  51. 19536493

    38655

    4

    19391

    30545

    Returns: -1

  52. 19536494

    38655

    4

    19391

    30545

    Returns: 834

  53. 23066289

    36448

    5

    31608

    22741

    Returns: -1

  54. 23066290

    36448

    5

    31608

    22741

    Returns: 732

  55. 18936461

    29745

    7

    17533

    24285

    Returns: -1

  56. 18936462

    29745

    7

    17533

    24285

    Returns: 645

  57. 4134259

    11755

    1

    18106

    20201

    Returns: -1

  58. 4134260

    11755

    1

    18106

    20201

    Returns: 894

  59. 10703057

    28847

    9

    17214

    3977

    Returns: -1

  60. 10703058

    28847

    9

    17214

    3977

    Returns: 425

  61. 3678282

    1901

    8

    8455

    22354

    Returns: -1

  62. 3678283

    1901

    8

    8455

    22354

    Returns: 113

  63. 13053345

    34937

    1

    35774

    34248

    Returns: 2036

  64. 14911911

    38094

    1

    37999

    38598

    Returns: 2150

  65. 14970055

    38854

    1

    39791

    36347

    Returns: 2064

  66. 13243161

    39967

    1

    31153

    35255

    Returns: 2223

  67. 15357711

    39918

    1

    38674

    38385

    Returns: 2230

  68. 402

    55

    1

    4

    53

    Returns: -1

  69. 403

    55

    1

    4

    53

    Returns: 36

  70. 693

    55

    1

    4

    53

    Returns: 6

  71. 352

    66

    1

    37

    8

    Returns: -1

  72. 353

    66

    1

    37

    8

    Returns: 26

  73. 495

    66

    1

    37

    8

    Returns: 8

  74. 781

    79

    1

    28

    64

    Returns: -1

  75. 782

    79

    1

    28

    64

    Returns: 33

  76. 1307

    79

    1

    28

    64

    Returns: 7

  77. 1089

    39

    1

    97

    91

    Returns: -1

  78. 1090

    39

    1

    97

    91

    Returns: 26

  79. 1952

    39

    1

    97

    91

    Returns: 5

  80. 490

    64

    1

    7

    57

    Returns: -1

  81. 491

    64

    1

    7

    57

    Returns: 30

  82. 836

    64

    1

    7

    57

    Returns: 6

  83. 404

    64

    1

    52

    1

    Returns: -1

  84. 405

    64

    1

    52

    1

    Returns: 36

  85. 468

    64

    1

    52

    1

    Returns: 11

  86. 703

    26

    1

    89

    62

    Returns: -1

  87. 704

    26

    1

    89

    62

    Returns: 17

  88. 1234

    26

    1

    89

    62

    Returns: 4

  89. 438

    27

    1

    85

    7

    Returns: -1

  90. 439

    27

    1

    85

    7

    Returns: 22

  91. 464

    27

    1

    85

    7

    Returns: 10

  92. 808

    88

    1

    11

    79

    Returns: -1

  93. 809

    88

    1

    11

    79

    Returns: 40

  94. 1580

    88

    1

    11

    79

    Returns: 6

  95. 739

    47

    1

    38

    77

    Returns: -1

  96. 740

    47

    1

    38

    77

    Returns: 25

  97. 1057

    47

    1

    38

    77

    Returns: 7

  98. 2

    2

    2

    2

    2

    Returns: -1

  99. 1

    2

    2

    2

    2

    Returns: -1

  100. 2

    1

    2

    2

    2

    Returns: -1

  101. 1

    1

    2

    2

    2

    Returns: -1

  102. 2

    2

    1

    2

    2

    Returns: -1

  103. 1

    2

    1

    2

    2

    Returns: -1

  104. 2

    1

    1

    2

    2

    Returns: -1

  105. 1

    1

    1

    2

    2

    Returns: -1

  106. 2

    2

    2

    1

    2

    Returns: -1

  107. 1

    2

    2

    1

    2

    Returns: -1

  108. 2

    1

    2

    1

    2

    Returns: -1

  109. 1

    1

    2

    1

    2

    Returns: -1

  110. 2

    2

    1

    1

    2

    Returns: -1

  111. 1

    2

    1

    1

    2

    Returns: -1

  112. 2

    1

    1

    1

    2

    Returns: -1

  113. 1

    1

    1

    1

    2

    Returns: -1

  114. 2

    2

    2

    2

    1

    Returns: -1

  115. 1

    2

    2

    2

    1

    Returns: -1

  116. 2

    1

    2

    2

    1

    Returns: -1

  117. 1

    1

    2

    2

    1

    Returns: -1

  118. 2

    2

    1

    2

    1

    Returns: -1

  119. 1

    2

    1

    2

    1

    Returns: -1

  120. 2

    1

    1

    2

    1

    Returns: -1

  121. 1

    1

    1

    2

    1

    Returns: -1

  122. 2

    2

    2

    1

    1

    Returns: -1

  123. 1

    2

    2

    1

    1

    Returns: -1

  124. 2

    1

    2

    1

    1

    Returns: 1

  125. 1

    1

    2

    1

    1

    Returns: -1

  126. 2

    2

    1

    1

    1

    Returns: -1

  127. 1

    2

    1

    1

    1

    Returns: -1

  128. 2

    1

    1

    1

    1

    Returns: 1

  129. 1

    1

    1

    1

    1

    Returns: -1

  130. 14877

    551

    86

    18

    9

    Returns: 1

  131. 43

    8

    3

    3

    6

    Returns: 3

  132. 13

    3

    13

    2

    3

    Returns: -1

  133. 4553

    55

    9

    92

    157

    Returns: 9

  134. 7850

    206

    3857

    30

    9

    Returns: 2

  135. 531144140

    60

    49

    85

    597

    Returns: 1

  136. 722639

    898

    26980

    196

    658

    Returns: -1

  137. 1000000000

    40000

    100

    1

    40000

    Returns: 2

  138. 97030319

    39222

    37805

    4

    3738

    Returns: 3

  139. 1000000000

    40000

    1

    40000

    40000

    Returns: 4

  140. 999999999

    39999

    39999

    39999

    39999

    Returns: -1

  141. 1000000000

    400

    2

    456

    65

    Returns: 1

  142. 500000000

    10000

    10000

    10000

    10000

    Returns: 1

  143. 100000

    10

    10

    10

    10

    Returns: 1

  144. 1000000000

    1

    1

    1

    1

    Returns: 1

  145. 1000000000

    111

    111

    222

    222

    Returns: 1

  146. 345243216

    35000

    7

    12555

    36987

    Returns: 6

  147. 1000000000

    9997

    39999

    39999

    39999

    Returns: 1

  148. 1000000000

    1

    1

    40000

    40000

    Returns: 1

  149. 1000000000

    43

    4

    664

    345

    Returns: 1

  150. 1000

    4000

    1

    3

    7

    Returns: 49

  151. 200

    1

    1

    1

    1

    Returns: 1

  152. 1000000000

    40000

    1000

    9999

    9192

    Returns: 1

  153. 1000000000

    1000

    500

    5000

    5000

    Returns: 1

  154. 5

    3

    2

    1

    1

    Returns: -1

  155. 1000000000

    10

    1

    100

    100

    Returns: 1

  156. 12

    3

    2

    1

    5

    Returns: 3

  157. 70000

    1

    1

    40000

    40000

    Returns: 2

  158. 1000000000

    40000

    40000

    40000

    39999

    Returns: -1

  159. 599990990

    100

    40000

    40000

    4000

    Returns: 1

  160. 7

    3

    2

    1

    2

    Returns: 2

  161. 12

    3

    2

    3

    3

    Returns: 2

  162. 4

    4

    1

    1

    1

    Returns: -1

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: