JOIN
Get Time

   Problem Statement  

 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

0)
    
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:
  1. Cat 0 is given the ball.
  2. Cat 0 flips the coin. The coin comes up tails.
  3. Cat 0 hands the ball to cat (0-1) mod 3 = cat 2.
  4. Cat 2 flips the coin. The comes up tails again.
  5. Cat 2 hands the ball to cat (2-1) mod 3 = cat 1.
  6. 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.
1)
    
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.
2)
    
6
5
500000000
Returns: 0.2
3)
    
10
2
666666666
Returns: 0.00391389439551009
4)
    
999999999
999999996
777777777
Returns: 0.05830903870125612
5)
    
1000000000
4
300000000
Returns: 0.044981259448371
6)
    
534428790
459947197
500000000
Returns: 1.871156682766205E-9

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.

This problem was used for:
       Single Round Match 667 Round 1 - Division I, Level Two