Statistics

Problem Statement for "WellTimedSearch"

Problem Statement

Monicka has an array of N cells, numbered 0 through N-1. She chooses one cell of the array uniformly at random and places a token into that cell.

Misko will then play a game with Monicka, trying to guess the location of the token. The gameplay is similar to binary searching for the token – in each turn, Misko picks a cell of the array and receives one of three possible answers: "left" if the token is in a cell with a smaller number, "right" if it is in a cell with a larger number, or "correct" if the chosen cell contains the token. The game ends when Misko gets the answer "correct".

Misko is not allowed to ask useless questions. For example, if he already chose the cell 47 and received the answer "right", he is not allowed to choose any of the cells 3, 12, and 47: it is already known that these cells do not contain the token.

Monicka does not like games that are too short or too long. She is happy with a game that takes at least A, but at most B turns. Misko wants to make Monicka happy, therefore he aims to finish the game in such a number of turns.

You are given the ints N, A, and B. Find the optimal strategy for Misko and return the probability that he will finish the game in at least A, but at most B turns.

Definition

Class:
WellTimedSearch
Method:
getProbability
Parameters:
int, int, int
Returns:
double
Method signature:
double getProbability(int N, int A, int B)
(be sure your method is public)

Notes

  • Return values with absolute or relative error at most 1e-9 will be accepted as correct.

Constraints

  • N will be between 1 and 1,000,000, inclusive.
  • A will be between 1 and N, inclusive.
  • B will be between A and N, inclusive.

Examples

  1. 3

    2

    2

    Returns: 0.6666666666666666

    Monicka will be happy if Misko's second guess is correct. The best strategy for Misko is to choose the index 1 first. If he gets the answer "correct", he won the game too early. But if he gets the answer "left" or "right", he will win the game in the second turn. Thus the probability that Monicka will be happy when Misko uses this strategy is 2/3.

  2. 3

    3

    3

    Returns: 0.3333333333333333

    This time Misko wants to postpone his correct guess until the third turn.

  3. 123456

    1

    20

    Returns: 1.0

    Misko can use binary search to guarantee that he will be able to guess Monicka's number in well under 20 guesses.

  4. 5

    3

    4

    Returns: 0.6

  5. 1

    1

    1

    Returns: 1.0

  6. 1000000

    3

    5

    Returns: 2.8E-5

  7. 1000000

    100000

    900000

    Returns: 0.900001

  8. 1000000

    100000

    100017

    Returns: 0.9

  9. 1000000

    100000

    100016

    Returns: 0.899997

  10. 1000000

    100000

    100015

    Returns: 0.899991

  11. 1000000

    7

    999947

    Returns: 0.999994

  12. 622760

    234

    628

    Returns: 0.999625859078939

  13. 212578

    50

    15775

    Returns: 0.999769496373096

  14. 40

    2

    11

    Returns: 0.975

  15. 104

    31

    44

    Returns: 0.7115384615384616

  16. 446

    14

    37

    Returns: 0.9708520179372198

  17. 46

    4

    14

    Returns: 0.9347826086956522

  18. 286135

    51

    51

    Returns: 0.4999318503503591

  19. 45

    31

    35

    Returns: 0.3333333333333333

  20. 988984

    6355

    6357

    Returns: 0.8693902024704141

  21. 25

    2

    14

    Returns: 0.96

  22. 77590

    931

    933

    Returns: 0.8646217296043305

  23. 221

    3

    15

    Returns: 0.9909502262443439

  24. 5606

    2281

    2296

    Returns: 0.5932929004637888

  25. 101

    21

    23

    Returns: 0.7227722772277227

  26. 146807

    163

    165

    Returns: 0.8740931971908696

  27. 4591

    29

    34

    Returns: 0.9793073404487039

  28. 48

    2

    13

    Returns: 0.9791666666666666

  29. 10977

    8746

    8772

    Returns: 0.20333424432905164

  30. 11

    1

    3

    Returns: 0.6363636363636364

  31. 2402

    7

    10

    Returns: 0.3996669442131557

  32. 903

    42

    51

    Returns: 0.9545957918050941

  33. 2740

    7

    374

    Returns: 0.9978102189781022

  34. 20828

    440

    481

    Returns: 0.9789226041866718

  35. 477

    27

    29

    Returns: 0.8343815513626834

  36. 139

    1

    4

    Returns: 0.1079136690647482

  37. 50425

    2257

    2262

    Returns: 0.9404462072384729

  38. 362802

    1

    16

    Returns: 0.18063571865645725

  39. 16669

    15

    25

    Returns: 0.9987401763753074

  40. 3910

    12

    19

    Returns: 0.9943734015345268

  41. 365461

    655

    658

    Returns: 0.9358372028752726

  42. 450897

    2752

    19730

    Returns: 0.9938988283355179

  43. 100283

    1

    5

    Returns: 3.091251757526201E-4

  44. 161

    7

    11

    Returns: 0.9440993788819876

  45. 491266

    54

    65

    Returns: 0.9996620975194701

  46. 115

    9

    10

    Returns: 0.7304347826086957

  47. 144

    58

    81

    Returns: 0.6041666666666666

  48. 24

    5

    18

    Returns: 0.8333333333333334

  49. 111736

    139

    105312

    Returns: 0.9987649459440109

  50. 670152

    1909

    1922

    Returns: 0.9970961811648701

  51. 3671

    18

    18

    Returns: 0.49850177063470447

  52. 767724

    579061

    579061

    Returns: 0.12287749243217615

  53. 527123

    10

    13

    Returns: 0.014569654520861355

  54. 12

    4

    10

    Returns: 0.75

  55. 50

    10

    24

    Returns: 0.82

  56. 1860

    291

    300

    Returns: 0.8440860215053764

  57. 12

    7

    8

    Returns: 0.5

  58. 525863

    37

    183

    Returns: 0.9999315411048124

  59. 7664

    385

    388

    Returns: 0.8913100208768268

  60. 23341

    1

    3

    Returns: 2.999014609485455E-4

  61. 22453

    12636

    12642

    Returns: 0.4340177259163586

  62. 231

    11

    14

    Returns: 0.9090909090909091

  63. 203

    1

    5

    Returns: 0.15270935960591134

  64. 39

    1

    6

    Returns: 1.0

  65. 176697

    40515

    40527

    Returns: 0.7706299484428145

  66. 444950

    1

    55

    Returns: 1.0

  67. 18597

    125

    128

    Returns: 0.9314405549282142

  68. 130892

    5

    10

    Returns: 0.0077010054090395135

  69. 942

    18

    27

    Returns: 0.9819532908704883

  70. 58

    12

    24

    Returns: 0.8103448275862069

  71. 301602

    20407

    20493

    Returns: 0.9323412974715022

  72. 96381

    17859

    17859

    Returns: 0.4073935734221475

  73. 573

    3

    109

    Returns: 0.9965095986038395

  74. 90

    35

    45

    Returns: 0.6222222222222222

  75. 843

    384

    388

    Returns: 0.5326215895610913

  76. 226

    5

    6

    Returns: 0.21238938053097345

  77. 41972

    41

    46

    Returns: 0.9835842942914323

  78. 92583

    470

    536

    Returns: 0.9949342751909098

  79. 45

    12

    19

    Returns: 0.7555555555555555

  80. 56

    9

    10

    Returns: 0.6785714285714286

  81. 35085

    454

    468

    Returns: 0.9870884993587002

  82. 304

    1

    15

    Returns: 1.0

  83. 228901

    4

    15

    Returns: 0.1431186408097824

  84. 1661

    154

    164

    Returns: 0.9078868151715834

  85. 12054

    2

    2

    Returns: 1.6592002654720425E-4

  86. 3730

    2391

    2406

    Returns: 0.35924932975871315

  87. 322999

    6

    496

    Returns: 0.9999845200759135

  88. 161738

    3

    13

    Returns: 0.050625085014035044

  89. 471754

    1

    10

    Returns: 0.0021685030757555845

  90. 12705

    1102

    1104

    Returns: 0.799685163321527

  91. 96

    56

    57

    Returns: 0.34375

  92. 108411

    5049

    47832

    Returns: 0.9534364593998764

  93. 464

    10

    21

    Returns: 0.9806034482758621

  94. 122

    62

    74

    Returns: 0.5

  95. 1005

    128

    134

    Returns: 0.8696517412935323

  96. 240881

    43

    58

    Returns: 0.9998214886188616

  97. 313456

    16

    31

    Returns: 0.9999425756725027

  98. 160109

    628

    1135

    Returns: 0.9960839178309776

  99. 59596

    20968

    20984

    Returns: 0.6481810859789248

  100. 14002

    12

    29

    Returns: 0.999214397943151

  101. 127

    7

    8

    Returns: 0.7480314960629921

  102. 241

    128

    133

    Returns: 0.4730290456431535

  103. 13

    7

    7

    Returns: 0.3076923076923077

  104. 3908

    31

    33

    Returns: 0.8697543500511771

  105. 24

    6

    20

    Returns: 0.7916666666666666

  106. 260076

    777

    799

    Returns: 0.9970162567864778

  107. 642

    2

    40

    Returns: 0.9984423676012462

  108. 827864

    15

    20

    Returns: 0.9843669974778466

  109. 97

    50

    92

    Returns: 0.4948453608247423

  110. 3906

    1013

    1029

    Returns: 0.7409114183307731

  111. 29379

    26643

    26651

    Returns: 0.09305966847067633

  112. 11

    4

    4

    Returns: 0.45454545454545453

  113. 1000000

    100000

    100010

    Returns: 0.899569

  114. 651345

    41234

    431234

    Returns: 0.9366956067828878

  115. 945817

    16352

    84572

    Returns: 0.9827123005824594

  116. 1000000

    15

    25

    Returns: 0.999503

  117. 888888

    393939

    737373

    Returns: 0.5568193068193068

  118. 1000000

    15

    20

    Returns: 0.984368

  119. 1000000

    16

    18

    Returns: 0.229376

  120. 100

    8

    10

    Returns: 0.84

  121. 10000

    37

    43

    Returns: 0.9891

  122. 123456

    1000

    10000

    Returns: 0.9919080482115086

  123. 745234

    30

    40

    Returns: 0.9994820418821471

  124. 1000000

    37

    43

    Returns: 0.992158

  125. 50

    18

    20

    Returns: 0.6

  126. 1000000

    1000000

    1000000

    Returns: 1.0E-6

  127. 50

    4

    6

    Returns: 0.86

  128. 1000000

    500000

    500000

    Returns: 0.250005

  129. 100

    5

    7

    Returns: 0.86

  130. 100000

    12

    17

    Returns: 0.98432

  131. 1000000

    100

    100

    Returns: 0.499956

  132. 16

    5

    5

    Returns: 0.5

  133. 1000000

    310879

    398810

    Returns: 0.689122

  134. 1000000

    1

    1000000

    Returns: 1.0

  135. 1000000

    1000

    1010

    Returns: 0.998521

  136. 1000000

    456123

    765948

    Returns: 0.543878

  137. 1000000

    500000

    500003

    Returns: 0.468758

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: