Statistics

Problem Statement for "BallsInBoxes"

Problem Statement

There are N boxes arranged in a row. The boxes are numbered 0 through N-1 from left to right.

Cat Snuke knows that exactly K consecutive boxes contain balls. Formally, there exists some i (0 <= i <= N-K) such that the boxes i, i+1, ..., i+K-1 contain balls while all others are empty.

He wants to determine which boxes contain balls. In each turn, he can choose a box, open it and check whether the box contains a ball or not. Note that the result of each turn may affect his future decisions about which boxes to open in the next turns.

How many turns are required to determine the positions of the balls in the worst case, assuming that Snuke uses the optimal strategy?

Definition

Class:
BallsInBoxes
Method:
maxTurns
Parameters:
long, long
Returns:
long
Method signature:
long maxTurns(long N, long K)
(be sure your method is public)

Constraints

  • N will be between 1 and 10^18, inclusive.
  • K will be between 1 and N, inculsive.

Examples

  1. 10

    10

    Returns: 0

    Snuke knows that all boxes contain balls, so he doesn't need to open any boxes.

  2. 100

    1

    Returns: 99

    In the worst case, if he opens 98 boxes and none of them contains the only ball, he can't determine which box contains the ball.

  3. 1000

    999

    Returns: 1

    There are two possibilities: Boxes 0, 1, ..., 998 contain balls. Boxes 1, 2, ..., 999 contain balls. He can determine the positions of the balls if he opens box 0.

  4. 1000000000000000000

    1

    Returns: 999999999999999999

  5. 1000000000000000000

    1000000000000000000

    Returns: 0

  6. 1000000000000000000

    12345

    Returns: 81004455245051

  7. 10

    5

    Returns: 3

  8. 1

    1

    Returns: 0

  9. 5027655433553

    2671676608

    Returns: 1912

  10. 630805811860343

    241744492147883

    Returns: 49

  11. 126628324358

    40

    Returns: 3165708113

  12. 168029527

    26

    Returns: 6462677

  13. 82232

    954

    Returns: 95

  14. 2325

    27

    Returns: 89

  15. 2207214334724016

    893478067082335

    Returns: 51

  16. 732788420489844992

    1209332270

    Returns: 605944680

  17. 6454676219505748

    5123

    Returns: 1259940702628

  18. 678913968068243

    14878534762064

    Returns: 88

  19. 14851331

    89

    Returns: 166874

  20. 7942128729133600

    1910975230

    Returns: 4156090

  21. 198794

    99

    Returns: 2013

  22. 1022567

    12

    Returns: 85216

  23. 6259879625284627

    34052

    Returns: 183832950363

  24. 163730420801634400

    18508386157

    Returns: 8846316

  25. 136809932934078560

    192796

    Returns: 709609810044

  26. 748263060606834432

    1877384457

    Returns: 398566800

  27. 30652807934750

    3

    Returns: 10217602644917

  28. 194470855179348096

    28155622907582572

    Returns: 60

  29. 1653921024699

    11

    Returns: 150356456793

  30. 147561379281945760

    20

    Returns: 7378068964097291

  31. 682683423959

    32797840536

    Returns: 54

  32. 843853

    14

    Returns: 60278

  33. 2810758689722

    1

    Returns: 2810758689721

  34. 843104905118044672

    3905966660197

    Returns: 215891

  35. 2101269805956626

    111

    Returns: 18930358612227

  36. 179099816959864

    161663381

    Returns: 1107882

  37. 3759051900717881

    2572685211045

    Returns: 1501

  38. 1595

    116

    Returns: 19

  39. 2189892418268766

    9

    Returns: 243321379807642

  40. 596929637353063

    863532998

    Returns: 691293

  41. 510628381635

    503718512

    Returns: 1041

  42. 2672451067

    515343843

    Returns: 33

  43. 2564086381269720

    187217435

    Returns: 13695793

  44. 1151004

    1945

    Returns: 601

  45. 226833200240

    19709544

    Returns: 11532

  46. 1084

    116

    Returns: 15

  47. 43740974459227264

    340209944423007

    Returns: 175

  48. 64236048894092792

    2

    Returns: 32118024447046396

  49. 17057602277

    2

    Returns: 8528801138

  50. 402050

    67946

    Returns: 20

  51. 382293665

    26159

    Returns: 14627

  52. 32

    22

    Returns: 4

  53. 8613744388

    126

    Returns: 68363056

  54. 236287986758

    112486953

    Returns: 2126

  55. 100

    1

    Returns: 99

  56. 253961593837797472

    8185238870791

    Returns: 31068

  57. 1948251853121

    2184285

    Returns: 891960

  58. 15326817705

    7122635533

    Returns: 33

  59. 999999999999999997

    37951

    Returns: 26349766804578

  60. 944115188075855871

    100000000000000000

    Returns: 64

  61. 999999999999999999

    3324

    Returns: 300842358604102

  62. 1000000000000000000

    1234567899

    Returns: 810000030

  63. 1000000000000

    5000000

    Returns: 200021

  64. 11

    5

    Returns: 3

  65. 11000000

    10

    Returns: 1100002

  66. 10

    6

    Returns: 3

  67. 999999999999999487

    97845321377

    Returns: 10220248

  68. 1000000000000000000

    4221

    Returns: 236910684671889

  69. 929332873854123812

    19283965

    Returns: 48192001712

  70. 60006000600060006

    5445344

    Returns: 11019689613

  71. 139

    40

    Returns: 7

  72. 38482906000000

    1099511627776

    Returns: 73

  73. 7

    3

    Returns: 3

  74. 10

    3

    Returns: 4

  75. 16

    5

    Returns: 4

  76. 1000000000000

    17

    Returns: 58823529414

  77. 11

    3

    Returns: 4

  78. 2048

    1024

    Returns: 11

  79. 12

    5

    Returns: 3

  80. 1000000000000000000

    500000000000000000

    Returns: 59

  81. 11

    4

    Returns: 3

  82. 10000000000

    2

    Returns: 5000000000

  83. 4

    2

    Returns: 2

  84. 929332873854123812

    3726717257482912

    Returns: 300

  85. 10

    2

    Returns: 5

  86. 65

    21

    Returns: 6

  87. 9

    2

    Returns: 4

  88. 14

    6

    Returns: 4

  89. 781624781647614

    7634

    Returns: 102387317492

  90. 80

    7

    Returns: 13

  91. 5

    3

    Returns: 2

  92. 384829060000000

    10995116277760

    Returns: 77

  93. 123456

    456

    Returns: 278

  94. 8

    2

    Returns: 4

  95. 100000000000000

    43651

    Returns: 2290898275

  96. 14

    5

    Returns: 4

  97. 1000

    5

    Returns: 201

  98. 9

    3

    Returns: 3

  99. 1000000000000000000

    999999999999999999

    Returns: 1

  100. 1000000000000000000

    576460752303423488

    Returns: 59

  101. 3

    2

    Returns: 1

  102. 13251234

    23

    Returns: 576144

  103. 6

    2

    Returns: 3

  104. 1000000000000000000

    50000000000

    Returns: 20000034

  105. 5

    2

    Returns: 2

  106. 900000004294967296

    3000000000

    Returns: 300000032

  107. 21

    10

    Returns: 4

  108. 553869300062833912

    64637801098948976

    Returns: 63

  109. 1234567898765

    658167578

    Returns: 1904

  110. 20

    11

    Returns: 4

  111. 48

    12

    Returns: 6

  112. 12938512

    324

    Returns: 39941

  113. 42

    30

    Returns: 4

  114. 391749387

    4890851

    Returns: 101

  115. 377

    74

    Returns: 10

  116. 1859

    51

    Returns: 41

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: