Statistics

Problem Statement for "BouncingDiceGame"

Problem Statement

The formerly celebrated general Archibald Waving has retired after losing the fifth army. His new peaceful lifestyle made him fond of board games. A particular one is a two player game in which each player has to take a checker across a sequence of cells on the board until reaching the final cell. There are n cells in the board and they are numbered from 1 to n. The dice in use has d faces and each number between 1 and d has the same probability of being the result of a dice throw. For fun purposes, Waving may play with insanely multi-faced dices. In each turn, a player throws a dice and then moves his piece up for as many positions as the face of the dice indicates. A player wins when he reaches the cell n.

Waving has been playing against his wife, Esther, who has added a new rule to the game called 'bouncing'. This rule comes into action when a player whose position is on the last cells of the board gets a dice value that is larger than necessary to reach the n-th cell. In that case, instead of winning the game, the player will bounce back to the previous cells.

Formally, if a is the current cell number in which the player's checker is located and b is the result of the dice throw then the following rules are used:
  • If a + b is less than n, the player moves the checker to cell (a + b).
  • If a + b is exactly n, the player moves the checker to cell n and hence wins the game.
  • If a + b is higher than n, the player moves the checker to cell (n - (a + b - n)).


Archibald has been wondering how does this rule affect the odds of winning the game at different states. You are given the number of cells n, the number of faces in the dice d, the cell on which Archibald's checker is currently located x and the cell on which Esther's checker is located y. Archibald is the next player to move. Return the probability of Archibald winning the game.

Definition

Class:
BouncingDiceGame
Method:
winProbability
Parameters:
int, int, int, int
Returns:
double
Method signature:
double winProbability(int n, int d, int x, int y)
(be sure your method is public)

Notes

  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • n will be between 10 and 5000, inclusive.
  • d, x and y will be between 1 and n-1, inclusive.

Examples

  1. 10

    6

    1

    1

    Returns: 0.5417251215862328

  2. 10

    2

    1

    1

    Returns: 0.6090494791666666

    With a two faces dice, the bouncing aspect of the game has less of an effect and thus the probability for the first player to win is larger.

  3. 100

    20

    1

    10

    Returns: 0.49158887163174947

  4. 10

    5

    9

    1

    Returns: 0.6943018666666667

    Even though Waving is one cell away from the goal cell, the probability is still far from 100% due to the bouncing rule.

  5. 4999

    4998

    325

    4807

    Returns: 0.5000500250125236

  6. 10

    3

    8

    7

    Returns: 0.5999999999999999

  7. 4282

    1

    1789

    236

    Returns: 1.0

  8. 50

    3

    11

    11

    Returns: 0.5534074929395681

  9. 517

    59

    86

    36

    Returns: 0.5177366722994075

  10. 111

    108

    105

    4

    Returns: 0.5023255813953483

  11. 4963

    11

    4957

    21

    Returns: 1.0

  12. 5000

    4946

    4604

    35

    Returns: 0.5001520010016038

  13. 3794

    131

    3793

    3467

    Returns: 0.5155135592904747

  14. 4998

    20

    8

    145

    Returns: 0.32619040687013406

  15. 617

    590

    497

    585

    Returns: 0.5004240882103497

  16. 4998

    4718

    4997

    4957

    Returns: 0.5000529941706561

  17. 11

    1

    10

    10

    Returns: 1.0

  18. 169

    157

    1

    168

    Returns: 0.49819449910426367

  19. 4976

    240

    67

    4975

    Returns: 0.4250742567378541

  20. 4987

    5

    4925

    179

    Returns: 1.0

  21. 4532

    4479

    1339

    4524

    Returns: 0.5000558222619513

  22. 900

    899

    897

    132

    Returns: 0.5002782415136304

  23. 31

    1

    2

    2

    Returns: 1.0

  24. 20

    3

    10

    19

    Returns: 0.13247604155494236

  25. 10

    9

    7

    1

    Returns: 0.5294117647058822

  26. 4997

    4983

    4990

    4996

    Returns: 0.5000501756146678

  27. 4979

    4970

    4974

    76

    Returns: 0.5000503068719387

  28. 953

    950

    1

    20

    Returns: 0.4997361498032994

  29. 29

    23

    27

    27

    Returns: 0.511111111111111

  30. 105

    24

    101

    5

    Returns: 0.631261340609021

  31. 369

    368

    15

    337

    Returns: 0.5006802721088466

  32. 2376

    1

    31

    1

    Returns: 1.0

  33. 850

    848

    849

    5

    Returns: 0.5002949852507383

  34. 13

    11

    12

    6

    Returns: 0.5238095238095238

  35. 4999

    4895

    4363

    2

    Returns: 0.500155340957824

  36. 10

    9

    3

    1

    Returns: 0.5294117647058822

  37. 10

    9

    1

    9

    Returns: 0.5294117647058822

  38. 4985

    336

    1

    21

    Returns: 0.5005625236630795

  39. 10

    9

    9

    9

    Returns: 0.5294117647058822

  40. 4079

    251

    13

    315

    Returns: 0.4962681084618545

  41. 4575

    111

    55

    489

    Returns: 0.46905069387567805

  42. 4979

    80

    3

    3032

    Returns: 0.1972416404285994

  43. 44

    5

    2

    1

    Returns: 0.5636737003261998

  44. 31

    5

    20

    8

    Returns: 0.8075156567437585

  45. 4904

    950

    620

    4601

    Returns: 0.4962355553861488

  46. 4999

    106

    4980

    2665

    Returns: 0.6665359227736856

  47. 4628

    3781

    4621

    25

    Returns: 0.5002304034336426

  48. 1866

    1666

    386

    40

    Returns: 0.5004801519161933

  49. 4411

    4226

    2647

    16

    Returns: 0.5001822617162464

  50. 4999

    1

    4980

    94

    Returns: 1.0

  51. 15

    1

    5

    2

    Returns: 1.0

  52. 4931

    3

    1165

    4699

    Returns: 1.225151568652548E-14

  53. 4994

    4903

    5

    31

    Returns: 0.5000504453664149

  54. 4904

    4785

    6

    14

    Returns: 0.5000520729072441

  55. 192

    188

    189

    37

    Returns: 0.5013333333333325

  56. 4246

    6

    1828

    4235

    Returns: 8.74512912905229E-15

  57. 10

    4

    9

    5

    Returns: 0.6785714285714286

  58. 11

    10

    9

    1

    Returns: 0.5263157894736842

  59. 20

    1

    15

    3

    Returns: 1.0

  60. 4972

    4652

    4967

    383

    Returns: 0.5000537461034041

  61. 961

    3

    2

    555

    Returns: 1.2884196631311012E-14

  62. 4994

    75

    24

    7

    Returns: 0.5057787515141474

  63. 5000

    30

    2324

    4968

    Returns: 0.0016296755583416565

  64. 23

    14

    22

    22

    Returns: 0.5185185185185186

  65. 4992

    36

    2081

    12

    Returns: 0.9777404449855197

  66. 857

    853

    1

    768

    Returns: 0.49970537050539676

  67. 151

    1

    21

    2

    Returns: 1.0

  68. 4951

    4950

    4931

    2

    Returns: 0.5000505101525353

  69. 4989

    4860

    12

    4913

    Returns: 0.4999460697708039

  70. 4217

    3794

    55

    4216

    Returns: 0.4999207166671611

  71. 256

    251

    226

    253

    Returns: 0.5009980039920157

  72. 4979

    1

    4955

    4943

    Returns: 1.0

  73. 4997

    4984

    118

    4342

    Returns: 0.5000501655463115

  74. 4995

    4989

    4912

    1

    Returns: 0.5001504060582014

  75. 89

    88

    1

    60

    Returns: 0.5028571428571434

  76. 233

    6

    181

    232

    Returns: 0.0479564522094032

  77. 4996

    4876

    11

    4641

    Returns: 0.4999464270890712

  78. 4158

    4080

    7

    311

    Returns: 0.49993659780959937

  79. 579

    24

    39

    1

    Returns: 0.5630317873723575

  80. 4979

    42

    3

    4944

    Returns: 0.0020182550913785775

  81. 107

    1

    10

    92

    Returns: 0.0

  82. 56

    7

    55

    1

    Returns: 0.9303502709270725

  83. 16

    15

    14

    15

    Returns: 0.5172413793103449

  84. 12

    2

    2

    1

    Returns: 0.7275975545247395

  85. 4452

    4241

    4430

    12

    Returns: 0.500182470197911

  86. 4993

    14

    3

    4992

    Returns: 2.421043186110378E-14

  87. 78

    3

    1

    12

    Returns: 0.13879150174121613

  88. 12

    11

    2

    1

    Returns: 0.5238095238095237

  89. 96

    18

    95

    14

    Returns: 0.6794711903037502

  90. 838

    1

    13

    648

    Returns: 0.0

  91. 1014

    188

    913

    1000

    Returns: 0.5013333333333323

  92. 4588

    4585

    11

    4584

    Returns: 0.5000545315737713

  93. 4999

    4797

    4953

    30

    Returns: 0.5001601232863107

  94. 983

    969

    468

    981

    Returns: 0.5002581311306173

  95. 4998

    4275

    4954

    118

    Returns: 0.5001931720843625

  96. 379

    88

    21

    22

    Returns: 0.5026793017175989

  97. 19

    2

    16

    2

    Returns: 0.9992806625862917

  98. 4945

    2

    96

    4929

    Returns: 3.0883696319750685E-15

  99. 3350

    3324

    198

    319

    Returns: 0.5000752219046236

  100. 4997

    92

    4967

    4876

    Returns: 0.5100242047150632

  101. 4998

    158

    4983

    20

    Returns: 0.6621142781770013

  102. 4136

    1

    12

    873

    Returns: 0.0

  103. 4722

    4665

    4662

    4523

    Returns: 0.5000535963125826

  104. 4943

    4171

    7

    4485

    Returns: 0.49991596464773047

  105. 5000

    1

    1

    1

    Returns: 1.0

  106. 5000

    1

    6

    1023

    Returns: 0.0

  107. 5000

    4999

    1

    1

    Returns: 0.5000500150045214

  108. 5000

    4999

    4987

    3989

    Returns: 0.500050015004498

  109. 5000

    2

    1

    1

    Returns: 0.5073113082435863

  110. 5000

    2

    6

    1

    Returns: 0.5558860062050883

  111. 5000

    4998

    1

    1

    Returns: 0.5000500250125232

  112. 5000

    4998

    4633

    2

    Returns: 0.5000500250125245

  113. 5000

    7

    1

    1

    Returns: 0.5075303452810015

  114. 5000

    4

    99

    4996

    Returns: 5.30291526129089E-15

  115. 5000

    4995

    1

    1

    Returns: 0.5000500550485313

  116. 5000

    4995

    39

    4937

    Returns: 0.5000500550605664

  117. 5000

    11

    1

    1

    Returns: 0.5078690102463322

  118. 5000

    11

    957

    231

    Returns: 0.9999703965761418

  119. 5000

    4991

    1

    1

    Returns: 0.5000500951527054

  120. 5000

    4991

    2

    4923

    Returns: 0.49994978433771564

  121. 5000

    22

    1

    1

    Returns: 0.5069627325671975

  122. 5000

    17

    4997

    19

    Returns: 0.999999999999999

  123. 5000

    4971

    1

    1

    Returns: 0.5000502966412351

  124. 5000

    4969

    210

    4999

    Returns: 0.5000503169970864

  125. 5000

    62

    1

    1

    Returns: 0.5035843381475031

  126. 5000

    39

    34

    4906

    Returns: 9.288889454447208E-4

  127. 5000

    4964

    1

    1

    Returns: 0.5000503675455915

  128. 5000

    4964

    4982

    18

    Returns: 0.5001514281604491

  129. 5000

    79

    1

    1

    Returns: 0.5029145622645638

  130. 5000

    105

    1

    497

    Returns: 0.460437033467684

  131. 5000

    4915

    1

    1

    Returns: 0.5000508695282901

  132. 5000

    4914

    150

    4739

    Returns: 0.5000508802279248

  133. 5000

    253

    1

    1

    Returns: 0.5009746851145893

  134. 5000

    214

    4999

    3

    Returns: 0.596193982024723

  135. 5000

    4820

    1

    1

    Returns: 0.500051871820614

  136. 5000

    4746

    4264

    4999

    Returns: 0.5000526814876965

  137. 5000

    262

    1

    1

    Returns: 0.5009419004907647

  138. 5000

    349

    4994

    1

    Returns: 0.538232158215041

  139. 5000

    4725

    1

    1

    Returns: 0.5000529143952079

  140. 5000

    4654

    10

    4990

    Returns: 0.49993826043859846

  141. 5000

    927

    1

    1

    Returns: 0.5002692640307708

  142. 5000

    872

    4

    53

    Returns: 0.5002219483141689

  143. 5000

    4447

    1

    1

    Returns: 0.5000562210510979

  144. 5000

    4322

    4195

    388

    Returns: 0.5001815204559087

  145. 5000

    3641

    1

    1

    Returns: 0.5000686602765231

  146. 5000

    2801

    4998

    4999

    Returns: 0.5000892697732565

  147. 4990

    77

    72

    4947

    Returns: 0.09883634771313736

  148. 4859

    4714

    1

    7

    Returns: 0.5000528994283812

  149. 5000

    2000

    100

    1

    Returns: 0.5001496698747883

  150. 4999

    4997

    1

    3

    Returns: 0.4999499649754471

  151. 5000

    2000

    1

    231

    Returns: 0.5000679445059347

  152. 5000

    3126

    4411

    2222

    Returns: 0.5000799872020449

  153. 5000

    1000

    4050

    200

    Returns: 0.5043613173564269

  154. 5000

    2500

    2

    3

    Returns: 0.5000997678547171

  155. 5000

    2000

    4900

    1

    Returns: 0.5010376579698138

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: