Statistics

Problem Statement for "MonstersAndBunnies"

Problem Statement

You just entered a strange town. The town is currently inhabited by M monsters and B bunnies.

The inhabitants interact in the following way: Whenever two bunnies meet, nothing happens. Whenever a monster meets a bunny, the monster eats the bunny. Whenever two monsters meet, they start fighting and they both die in the fight.

Whenever you meet a bunny, you can decide whether you kill it or not. A bunny will never kill you. You cannot kill a monster. However, if you meet a monster, it will kill you without hesitation.

All the town's inhabitants roam the town at random. More precisely, we will make the following assumptions.

  • Meetings will occur at different moments in time.
  • Each time exactly two beings will meet.
  • Those two beings are always chosen uniformly at random from the set of all living beings in town, including you.
  • All random choices are mutually independent.

You win if at some moment you can not be killed anymore. You are not allowed to leave the town until you either win or get killed.

Write a method that will calculate the probability that you will win if you make the best decisions you can.

Definition

Class:
MonstersAndBunnies
Method:
survivalProbability
Parameters:
int, int
Returns:
double
Method signature:
double survivalProbability(int M, int B)
(be sure your method is public)

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.
  • When deciding whether to kill a bunny you just met, your only goal is to maximize your winning probability.

Constraints

  • M will be between 0 and 1,000, inclusive.
  • B will be between 0 and 1,000, inclusive.

Examples

  1. 0

    0

    Returns: 1.0

    This town is empty. As soon as you enter it, you win.

  2. 0

    47

    Returns: 1.0

    Peaceful bunny pastures, you will not get killed here.

  3. 1

    0

    Returns: 0.0

    Sooner or later the monster will find you and kill you.

  4. 1

    47

    Returns: 0.0

    The bunnies won't help you. Sooner or later the monster will find you and kill you.

  5. 2

    0

    Returns: 0.3333333333333333

    In 1/3 of all cases the two monsters meet first, kill each other and you win. In the other 2/3 cases, one of the two monsters meets you first and kills you.

  6. 999

    987

    Returns: 0.0

  7. 1000

    1000

    Returns: 9.99000999000999E-4

  8. 1000

    0

    Returns: 9.99000999000999E-4

  9. 0

    1000

    Returns: 1.0

  10. 1

    1

    Returns: 0.0

  11. 0

    1

    Returns: 1.0

  12. 3

    0

    Returns: 0.0

  13. 4

    1

    Returns: 0.2

  14. 5

    5

    Returns: 0.0

  15. 15

    155

    Returns: 0.0

  16. 988

    976

    Returns: 0.0010111223458038423

  17. 946

    235

    Returns: 0.0010559662090813093

  18. 235

    946

    Returns: 0.0

  19. 987

    987

    Returns: 0.0

  20. 32

    325

    Returns: 0.030303030303030304

  21. 86

    456

    Returns: 0.011494252873563218

  22. 4

    2

    Returns: 0.2

  23. 100

    100

    Returns: 0.009900990099009901

  24. 1000

    988

    Returns: 9.99000999000999E-4

  25. 999

    999

    Returns: 0.0

  26. 4

    666

    Returns: 0.2

  27. 6

    991

    Returns: 0.14285714285714285

  28. 900

    17

    Returns: 0.0011098779134295228

  29. 988

    917

    Returns: 0.0010111223458038423

  30. 4

    12

    Returns: 0.2

  31. 10

    10

    Returns: 0.09090909090909091

  32. 100

    1

    Returns: 0.009900990099009901

  33. 992

    654

    Returns: 0.0010070493454179255

  34. 20

    20

    Returns: 0.047619047619047616

  35. 850

    300

    Returns: 0.0011750881316098707

  36. 900

    1000

    Returns: 0.0011098779134295228

  37. 100

    0

    Returns: 0.009900990099009901

  38. 418

    998

    Returns: 0.002386634844868735

  39. 11

    999

    Returns: 0.0

  40. 998

    1000

    Returns: 0.001001001001001001

  41. 10

    100

    Returns: 0.09090909090909091

  42. 2

    1

    Returns: 0.3333333333333333

  43. 56

    28

    Returns: 0.017543859649122806

  44. 998

    999

    Returns: 0.001001001001001001

  45. 300

    300

    Returns: 0.0033222591362126247

  46. 2

    10

    Returns: 0.3333333333333333

  47. 1000

    599

    Returns: 9.99000999000999E-4

  48. 800

    500

    Returns: 0.0012484394506866417

  49. 376

    224

    Returns: 0.002652519893899204

  50. 972

    914

    Returns: 0.0010277492291880781

  51. 300

    1000

    Returns: 0.0033222591362126247

  52. 2

    2

    Returns: 0.3333333333333333

  53. 4

    0

    Returns: 0.2

  54. 900

    123

    Returns: 0.0011098779134295228

  55. 100

    67

    Returns: 0.009900990099009901

  56. 1000

    999

    Returns: 9.99000999000999E-4

  57. 984

    383

    Returns: 0.0010152284263959391

  58. 6

    2

    Returns: 0.14285714285714285

  59. 820

    717

    Returns: 0.001218026796589525

  60. 2

    5

    Returns: 0.3333333333333333

  61. 786

    952

    Returns: 0.0012706480304955528

  62. 4

    4

    Returns: 0.2

  63. 200

    200

    Returns: 0.004975124378109453

  64. 2

    3

    Returns: 0.3333333333333333

  65. 6

    954

    Returns: 0.14285714285714285

  66. 320

    436

    Returns: 0.003115264797507788

  67. 10

    1

    Returns: 0.09090909090909091

  68. 34

    22

    Returns: 0.02857142857142857

  69. 68

    56

    Returns: 0.014492753623188406

  70. 4

    5

    Returns: 0.2

  71. 10

    0

    Returns: 0.09090909090909091

  72. 999

    0

    Returns: 0.0

  73. 3

    10

    Returns: 0.0

  74. 55

    100

    Returns: 0.0

  75. 500

    497

    Returns: 0.001996007984031936

  76. 851

    320

    Returns: 0.0

  77. 436

    123

    Returns: 0.002288329519450801

  78. 33

    5

    Returns: 0.0

  79. 4

    999

    Returns: 0.2

  80. 1000

    34

    Returns: 9.99000999000999E-4

  81. 100

    200

    Returns: 0.009900990099009901

  82. 124

    123

    Returns: 0.0080

  83. 248

    533

    Returns: 0.004016064257028112

  84. 22

    67

    Returns: 0.043478260869565216

  85. 8

    4

    Returns: 0.1111111111111111

  86. 4

    3

    Returns: 0.2

  87. 2

    1000

    Returns: 0.3333333333333333

  88. 20

    15

    Returns: 0.047619047619047616

  89. 973

    914

    Returns: 0.0

  90. 88

    112

    Returns: 0.011235955056179775

  91. 990

    999

    Returns: 0.0010090817356205853

  92. 990

    990

    Returns: 0.0010090817356205853

  93. 4

    16

    Returns: 0.2

  94. 5

    30

    Returns: 0.0

  95. 50

    5

    Returns: 0.0196078431372549

  96. 4

    100

    Returns: 0.2

  97. 4

    1000

    Returns: 0.2

  98. 788

    1000

    Returns: 0.0012674271229404308

  99. 1000

    400

    Returns: 9.99000999000999E-4

  100. 70

    69

    Returns: 0.014084507042253521

  101. 322

    212

    Returns: 0.0030959752321981426

  102. 158

    245

    Returns: 0.006289308176100629

  103. 2

    100

    Returns: 0.3333333333333333

  104. 100

    20

    Returns: 0.009900990099009901

  105. 984

    374

    Returns: 0.0010152284263959391

  106. 3

    2

    Returns: 0.0

  107. 6

    500

    Returns: 0.14285714285714285

  108. 1000

    100

    Returns: 9.99000999000999E-4

  109. 1000

    970

    Returns: 9.99000999000999E-4

  110. 500

    1

    Returns: 0.001996007984031936

  111. 850

    320

    Returns: 0.0011750881316098707

  112. 120

    120

    Returns: 0.008264462809917356

  113. 68

    23

    Returns: 0.014492753623188406

  114. 4

    20

    Returns: 0.2

  115. 28

    24

    Returns: 0.034482758620689655

  116. 42

    50

    Returns: 0.023255813953488372

  117. 978

    617

    Returns: 0.0010214504596527069

  118. 7

    5

    Returns: 0.0

  119. 966

    765

    Returns: 0.001034126163391934

  120. 956

    941

    Returns: 0.0010449320794148381

  121. 49

    99

    Returns: 0.0

  122. 444

    666

    Returns: 0.0022471910112359553

  123. 500

    34

    Returns: 0.001996007984031936

  124. 42

    40

    Returns: 0.023255813953488372

  125. 232

    34

    Returns: 0.004291845493562232

  126. 40

    10

    Returns: 0.024390243902439025

  127. 50

    50

    Returns: 0.0196078431372549

  128. 16

    4

    Returns: 0.058823529411764705

  129. 998

    850

    Returns: 0.001001001001001001

  130. 10

    20

    Returns: 0.09090909090909091

  131. 900

    900

    Returns: 0.0011098779134295228

  132. 2

    7

    Returns: 0.3333333333333333

  133. 124

    343

    Returns: 0.0080

  134. 425

    451

    Returns: 0.0

  135. 234

    123

    Returns: 0.00425531914893617

  136. 456

    223

    Returns: 0.002188183807439825

  137. 90

    8

    Returns: 0.01098901098901099

  138. 70

    56

    Returns: 0.014084507042253521

  139. 1000

    977

    Returns: 9.99000999000999E-4

  140. 900

    500

    Returns: 0.0011098779134295228

  141. 4

    120

    Returns: 0.2

  142. 4

    10

    Returns: 0.2

  143. 8

    8

    Returns: 0.1111111111111111

  144. 4

    125

    Returns: 0.2

  145. 868

    944

    Returns: 0.0011507479861910242

  146. 16

    28

    Returns: 0.058823529411764705

  147. 2

    71

    Returns: 0.3333333333333333

  148. 3

    1

    Returns: 0.0

  149. 66

    100

    Returns: 0.014925373134328358

  150. 122

    345

    Returns: 0.008130081300813009

  151. 900

    0

    Returns: 0.0011098779134295228

  152. 30

    13

    Returns: 0.03225806451612903

  153. 480

    100

    Returns: 0.002079002079002079

  154. 11

    1

    Returns: 0.0

  155. 400

    1000

    Returns: 0.0024937655860349127

  156. 102

    999

    Returns: 0.009708737864077669

  157. 444

    444

    Returns: 0.0022471910112359553

  158. 7

    3

    Returns: 0.0

  159. 12

    1

    Returns: 0.07692307692307693

  160. 12

    11

    Returns: 0.07692307692307693

  161. 1000

    74

    Returns: 9.99000999000999E-4

  162. 988

    988

    Returns: 0.0010111223458038423

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: