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.
|Parameters:||int, int, int|
|Method signature:||double getProb(int N, int K, int p)|
|(be sure your method is public)|
|-||Your return value must have an absolute or relative error smaller than or equal to 1e-6|
|-||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.|
|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:
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.
- 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.
|The coin that is flipped will come up heads with probability 1/2, and tails with probability 1/2. |
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)2010, TopCoder, Inc. All rights reserved.