Statistics

Problem Statement for "CatsOnTheCircle"

Problem Statement

There are N cats sitting around a circle. The cats are numbered 0 through N-1 in clockwise order. Note that as they sit around a circle, cat N-1 is adjacent to cat 0. The cats are playing a game and the winner will get a prize!

The game looks as follows:

  • There is a single ball. Initially, cat 0 holds the ball.
  • In each round of the game, the cat who currently holds a ball flips a biased coin. The coin will come up heads with probability p/1,000,000,000 and tails with probability 1-(p/1,000,000,000).
  • If the coin came up heads, the current cat will hand the ball to the next cat clockwise, otherwise the current cat will hand the ball to the next cat counterclockwise. Formally, if the current cat is cat j, heads means that the ball goes to cat (j+1) mod N and tails means that it goes to cat (j-1) mod N.
  • The game is played until each cat held the ball at least once. The cat who holds the ball at the end of the game is the winner.

In other words, the winner is the last cat to touch the ball. Note that cat 0 holds the ball at the beginning, and this does count as holding the ball. Hence, if there is more than one cat, cat 0 can never win the game.

Cat K wonders what is the probability that she will win the prize. You are given the ints N, K, and p. Return the probability that cat K wins.

Definition

Class:
CatsOnTheCircle
Method:
getProb
Parameters:
int, int, int
Returns:
double
Method signature:
double getProb(int N, int K, int p)
(be sure your method is public)

Notes

  • Your return value must have an absolute or relative error smaller than or equal to 1e-6

Constraints

  • N will be between 3 and 1,000,000,000, inclusive.
  • K will be between 1 and N-1, inclusive.
  • p will be between 1 and 999,999,999, inclusive.

Examples

  1. 3

    1

    300000000

    Returns: 0.6999999999999985

    This game has N=3 cats, labeled 0, 1, 2. We have p=30,000,000, hence the coin will come up heads with probability 30,000,000/1,000,000,000 = 0.3 and tails with probability 0.7. The game can look as follows: Cat 0 is given the ball. Cat 0 flips the coin. The coin comes up tails. Cat 0 hands the ball to cat (0-1) mod 3 = cat 2. Cat 2 flips the coin. The comes up tails again. Cat 2 hands the ball to cat (2-1) mod 3 = cat 1. At this moment, each cat has held the ball. The game ends and cat 1 gets the prize. This particular sequence of events has probability 0.7*0.7 of occuring. It can be shown that the probability that cat 1 wins the game is 0.7.

  2. 6

    2

    500000000

    Returns: 0.2

    The coin that is flipped will come up heads with probability 1/2, and tails with probability 1/2.

  3. 6

    5

    500000000

    Returns: 0.2

  4. 10

    2

    666666666

    Returns: 0.00391389439551009

  5. 999999999

    999999996

    777777777

    Returns: 0.05830903870125612

  6. 1000000000

    4

    300000000

    Returns: 0.044981259448371

  7. 845

    610

    500000000

    Returns: 0.001184834123222749

  8. 284

    148

    500000000

    Returns: 0.0035335689045936395

  9. 794001

    608362

    500000000

    Returns: 1.2594458438287154E-6

  10. 591336

    515437

    500000000

    Returns: 1.6910888075287274E-6

  11. 69073

    41054

    500000000

    Returns: 1.447764651378272E-5

  12. 23416

    22072

    500000000

    Returns: 4.2707666026051675E-5

  13. 4

    1

    500000000

    Returns: 0.3333333333333333

  14. 4

    3

    500000000

    Returns: 0.3333333333333333

  15. 534428790

    459947197

    500000000

    Returns: 1.871156682766205E-9

  16. 982563236

    782011669

    500000000

    Returns: 1.017746201342451E-9

  17. 72

    6

    500057696

    Returns: 0.013987173023992215

  18. 83

    65

    500000635

    Returns: 0.012195849875099264

  19. 6

    3

    499999649

    Returns: 0.20000000015339495

  20. 9

    6

    500000003

    Returns: 0.12499999197898548

  21. 50

    13

    499999841

    Returns: 0.020408319043968216

  22. 72

    6

    500057696

    Returns: 0.013987173023992215

  23. 83

    65

    500000635

    Returns: 0.012195849875099264

  24. 6

    3

    499999649

    Returns: 0.20000000015339495

  25. 441

    1

    7687475

    Returns: 0.9922529698997823

  26. 915

    807

    989178081

    Returns: 0.0

  27. 151

    22

    137093050

    Returns: 1.4026270808162948E-17

  28. 897

    17

    248333695

    Returns: 1.3489600057047522E-8

  29. 202

    201

    919974748

    Returns: 0.9130136428483797

  30. 115

    111

    394965710

    Returns: 1.4666130959769523E-21

  31. 891

    820

    792515863

    Returns: 0.0

  32. 743

    628

    649708978

    Returns: 0.0

  33. 673

    672

    667304024

    Returns: 0.5014326843022171

  34. 737

    703

    524722984

    Returns: 0.003595445597738331

  35. 591

    398

    500000011

    Returns: 0.001694922893499762

  36. 68

    7

    499999888

    Returns: 0.014925553737463376

  37. 882

    353

    499999981

    Returns: 0.0011350813293433384

  38. 611

    477

    499999985

    Returns: 0.0016393273558233965

  39. 764

    247

    505948349

    Returns: 1.0941199726007754E-7

  40. 523

    185

    500006553

    Returns: 0.0019118563336444926

  41. 722081921

    1

    112

    Returns: 0.999999887999997

  42. 518735821

    4

    2

    Returns: 0.0

  43. 776472446

    4

    2185

    Returns: 1.0431727211550238E-17

  44. 938104950

    938104948

    999999955

    Returns: 4.499999999999963E-8

  45. 436335849

    3

    513

    Returns: 2.6316913500569637E-13

  46. 14200288

    3

    15289

    Returns: 2.337570948575803E-10

  47. 694112130

    694112127

    999999941

    Returns: 3.4810002053790113E-15

  48. 243081943

    243081941

    999999998

    Returns: 1.999999999999998E-9

  49. 797124457

    1

    820238

    Returns: 0.9991790886204792

  50. 553884294

    553884291

    996262875

    Returns: 1.4018294869996601E-5

  51. 1000000000

    1

    1

    Returns: 0.9999999989999999

  52. 1000000000

    999999999

    999999999

    Returns: 0.9999999989999999

  53. 1000000000

    2

    489

    Returns: 4.889999999998763E-7

  54. 1000000000

    3

    19

    Returns: 3.61000006859001E-16

  55. 1000000000

    2

    1

    Returns: 1.0000000000000007E-9

  56. 1000000000

    999999998

    990275987

    Returns: 0.009723075378370841

  57. 1000000000

    999999997

    972278274

    Returns: 7.897629413254834E-4

  58. 123123

    1232

    1323221

    Returns: 0.0

  59. 1000000000

    800000000

    999999000

    Returns: 0.0

  60. 1000

    500

    500000000

    Returns: 0.001001001001001001

  61. 2005

    1001

    500000000

    Returns: 4.99001996007984E-4

  62. 1000000000

    500000000

    959595959

    Returns: 0.0

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: