Statistics

Problem Statement for "SubdividedSlimes"

Problem Statement

The idols Ami and Mami like playing games. Today they bought a new game. At the beginning of the game a single slime appears on the screen. You are given an int S: the size of the slime.

The game consists of K turns. In each turn of the game the player must choose a single slime and cut it into two smaller parts. More precisely, suppose that the player chose a slime of size z. When cutting this slime, the player must choose two positive integers x and y such that x+y = z. The player will then cut the slime into two smaller slimes. The sizes of those smaller slimes will be x and y, respectively. Note that the player must always choose a slime of size 2 or more, as it is not possible to cut a slime of size 1.

The player gets a reward for making each cut: whenever you cut a slime of size x+y into slimes of sizes x and y, the player is awarded x*y mascots.

Ami and Mami have just started a new game. You are given two ints S and M. Calculate and return the smallest possible K (the number of turns in the game) such that Ami and Mami can get at least M mascots in the game. If there exists no such K, return -1 instead.

Definition

Class:
SubdividedSlimes
Method:
needCut
Parameters:
int, int
Returns:
int
Method signature:
int needCut(int S, int M)
(be sure your method is public)

Constraints

  • S will be between 2 and 1000, inclusive.
  • M will be between 1 and 10^9, inclusive.

Examples

  1. 3

    2

    Returns: 1

    There is a single slime of size 3, and the players have to get at least two mascots. In this case, K = 1 is sufficient. In the only step, cut the only slime into two slimes with sizes 1 and 2. (This gives them 1*2 = 2 mascots.)

  2. 3

    3

    Returns: 2

    There is a single slime of size 3, and the players have to get at least three mascots. They can get three mascots in two steps: In the first step, cut the only slime into two slimes with sizes 1 and 2. (This gives them 1*2 = 2 mascots.) In the second step, choose the slime of size 2 and cut it into two slimes of size 1 each. (This gives them 1*1 = 1 mascot.) The total number of mascots they obtained is 2 + 1 = 3.

  3. 3

    4

    Returns: -1

    There is a single slime of size 3. The players cannot get 4 mascots in any way.

  4. 765

    271828

    Returns: 14

  5. 2

    1

    Returns: 1

  6. 2

    2

    Returns: -1

  7. 2

    4

    Returns: -1

  8. 2

    1000000000

    Returns: -1

  9. 5

    11

    Returns: -1

  10. 5

    10

    Returns: 4

  11. 5

    9

    Returns: 3

  12. 5

    8

    Returns: 2

  13. 5

    7

    Returns: 2

  14. 5

    6

    Returns: 1

  15. 5

    5

    Returns: 1

  16. 5

    4

    Returns: 1

  17. 5

    3

    Returns: 1

  18. 5

    2

    Returns: 1

  19. 5

    1

    Returns: 1

  20. 1000

    1

    Returns: 1

  21. 1000

    999

    Returns: 1

  22. 1000

    1000

    Returns: 1

  23. 1000

    250000

    Returns: 1

  24. 1000

    250001

    Returns: 2

  25. 1000

    333333

    Returns: 2

  26. 1000

    333334

    Returns: 3

  27. 1000

    416666

    Returns: 5

  28. 1000

    416667

    Returns: 6

  29. 1000

    431241

    Returns: 7

  30. 1000

    490000

    Returns: 49

  31. 1000

    490001

    Returns: 50

  32. 1000

    490002

    Returns: 50

  33. 1000

    499015

    Returns: 514

  34. 1000

    499498

    Returns: 997

  35. 1000

    499499

    Returns: 998

  36. 1000

    499500

    Returns: 999

  37. 1000

    499501

    Returns: -1

  38. 1000

    1000000000

    Returns: -1

  39. 118

    6808

    Returns: 46

  40. 118

    6809

    Returns: 47

  41. 383

    73058

    Returns: 287

  42. 383

    73059

    Returns: 288

  43. 870

    377550

    Returns: 424

  44. 870

    377551

    Returns: 425

  45. 546

    148572

    Returns: 332

  46. 546

    148573

    Returns: 333

  47. 340

    57563

    Returns: 272

  48. 340

    57564

    Returns: 273

  49. 305

    44185

    Returns: 19

  50. 305

    44186

    Returns: 20

  51. 719

    258079

    Returns: 676

  52. 719

    258080

    Returns: 677

  53. 116

    6618

    Returns: 63

  54. 116

    6619

    Returns: 64

  55. 890

    395335

    Returns: 619

  56. 890

    395336

    Returns: 620

  57. 772

    297250

    Returns: 415

  58. 772

    297251

    Returns: 416

  59. 151

    11307

    Returns: 132

  60. 151

    11308

    Returns: 133

  61. 82

    3163

    Returns: 16

  62. 82

    3164

    Returns: 17

  63. 557

    154682

    Returns: 392

  64. 557

    154683

    Returns: 393

  65. 848

    350560

    Returns: 39

  66. 848

    350561

    Returns: 40

  67. 348

    59643

    Returns: 66

  68. 348

    59644

    Returns: 67

  69. 772

    297518

    Returns: 683

  70. 772

    297519

    Returns: 684

  71. 626

    195495

    Returns: 495

  72. 626

    195496

    Returns: 496

  73. 491

    119800

    Returns: 162

  74. 491

    119801

    Returns: 163

  75. 170

    14346

    Returns: 150

  76. 170

    14347

    Returns: 151

  77. 161

    12877

    Returns: 157

  78. 161

    12878

    Returns: 158

  79. 661

    217928

    Returns: 458

  80. 661

    217929

    Returns: 459

  81. 281

    36847

    Returns: 14

  82. 281

    36848

    Returns: 15

  83. 624

    194212

    Returns: 459

  84. 624

    194213

    Returns: 460

  85. 582

    141135

    Returns: 5

  86. 582

    141136

    Returns: 6

  87. 158

    14613

    Returns: -1

  88. 338

    15269

    Returns: 1

  89. 109

    8714

    Returns: -1

  90. 273

    10398

    Returns: 1

  91. 353

    2567

    Returns: 1

  92. 24

    329

    Returns: -1

  93. 756

    23117

    Returns: 1

  94. 116

    8666

    Returns: -1

  95. 341

    25484

    Returns: 1

  96. 110

    2029

    Returns: 1

  97. 26

    339

    Returns: -1

  98. 659

    122

    Returns: 1

  99. 238

    19249

    Returns: 3

  100. 984

    20990

    Returns: 1

  101. 613

    27915

    Returns: 1

  102. 804

    5499

    Returns: 1

  103. 21

    155

    Returns: 3

  104. 563

    4555

    Returns: 1

  105. 536

    31144

    Returns: 1

  106. 350

    21152

    Returns: 1

  107. 576

    13201

    Returns: 1

  108. 365

    16079

    Returns: 1

  109. 240

    16732

    Returns: 2

  110. 728

    26863

    Returns: 1

  111. 657

    12127

    Returns: 1

  112. 77

    2131

    Returns: 3

  113. 742

    149134

    Returns: 2

  114. 310

    32004

    Returns: 2

  115. 898

    214488

    Returns: 2

  116. 608

    116376

    Returns: 2

  117. 347

    39759

    Returns: 2

  118. 166

    12330

    Returns: 9

  119. 600

    119097

    Returns: 2

  120. 492

    82060

    Returns: 3

  121. 399

    69761

    Returns: 8

  122. 491

    88195

    Returns: 3

  123. 488

    83417

    Returns: 3

  124. 275

    24493

    Returns: 2

  125. 109

    2995

    Returns: 2

  126. 404

    54519

    Returns: 3

  127. 98

    4358

    Returns: 10

  128. 380

    38332

    Returns: 2

  129. 291

    28305

    Returns: 3

  130. 73

    1716

    Returns: 2

  131. 957

    245518

    Returns: 2

  132. 400

    58829

    Returns: 3

  133. 463

    68943

    Returns: 2

  134. 970

    266687

    Returns: 2

  135. 897

    220235

    Returns: 2

  136. 646

    122042

    Returns: 2

  137. 20

    133

    Returns: 2

  138. 6

    12

    Returns: 2

  139. 100

    3300

    Returns: 2

  140. 8

    21

    Returns: 2

  141. 1000

    489999

    Returns: 49

  142. 1000

    495964

    Returns: 123

  143. 9

    27

    Returns: 2

  144. 12

    48

    Returns: 2

  145. 24

    192

    Returns: 2

  146. 10

    33

    Returns: 2

  147. 11

    40

    Returns: 2

  148. 12

    47

    Returns: 2

  149. 24

    240

    Returns: 5

  150. 90

    2600

    Returns: 2

  151. 10

    32

    Returns: 2

  152. 100

    3126

    Returns: 2

  153. 1000

    400000

    Returns: 4

  154. 32

    321

    Returns: 2

  155. 1000

    491221

    Returns: 56

  156. 100

    3149

    Returns: 2

  157. 21

    147

    Returns: 2

  158. 100

    3325

    Returns: 2

  159. 527

    130696

    Returns: 16

  160. 200

    13125

    Returns: 2

  161. 10

    40

    Returns: 4

  162. 20

    171

    Returns: 6

  163. 21

    145

    Returns: 2

  164. 765

    195075

    Returns: 2

  165. 1000

    477777

    Returns: 22

  166. 302

    30401

    Returns: 2

  167. 400

    50197

    Returns: 2

  168. 1000

    499001

    Returns: 500

  169. 1000

    499300

    Returns: 799

  170. 1000

    499449

    Returns: 948

  171. 10

    41

    Returns: 5

  172. 530

    90200

    Returns: 2

  173. 35

    501

    Returns: 5

  174. 1000

    499400

    Returns: 899

  175. 21

    215

    Returns: -1

  176. 1000

    499359

    Returns: 858

  177. 1000

    470000

    Returns: 16

  178. 99

    3267

    Returns: 2

  179. 25

    250

    Returns: 4

  180. 100

    4000

    Returns: 4

  181. 999

    332667

    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: