Problem Statement
N bears are standing around a circle and playing a game. Before the game started, the bears have chosen a positive integer K.
The game is played as follows: Limak, who is one of the N bears, will start the game by saying the number 1. The game then goes clockwise around the circle: the next bear clockwise from Limak will say 2, his other neighbor will say 3, and so on.
The bear who says the chosen number K must toss a fair coin and call heads or tails. If he loses the coin flip, he loses and he is removed from the game. If he wins the flip, he remains in the game. Regardless of the outcome of the coin flip, the game continues with the next bear in clockwise order. That bear will now start counting from 1 again.
The last bear who remains in the game is the winner. Can you find the probability that Limak will win?
You are given the
Definition
- Class:
- BearCircleGame
- Method:
- winProbability
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int winProbability(int n, int k)
- (be sure your method is public)
Notes
- Note the unusual Time Limit.
Constraints
- N will be between 2 and 2000, inclusive.
- K will be between 1 and 1,000,000,000, inclusive.
Examples
2
1
Returns: 333333336
As K=1, as the game goes around the circle, each bear says "1" and then flips a coin to see whether they lose. With N=2 bears we can count as follows: With probability 1/2, Limak loses the game in the first coin flip. With probability 1/4, Limak wins his flip and then his opponent loses. With probability 1/8, Limak and his opponent both win their first flip, and then Limak loses his second flip. ... and so on. Thus, the total probability that Limak wins the game is 1/4 + 1/16 + 1/64 + 1/256 + ... = 1/3.
2
2
Returns: 1
Limak will say 1. His opponent will say 2 and flip a coin. If the opponent loses the flip, Limak wins the game. Otherwise, the same process is repeated once again. Limak cannot lose this game. He will win it with probability 1.
3
2
Returns: 142857144
The answer is 1/7. Let's analyze one of possible scenarios. Let's says that players have names Limak, A and B. Limak says 1. A says 2, flips a coin and loses. You can notice that Limak can't win this game anymore. B says 1. Limak says 2, flips a coin and survives. B says 1. Limak says 2, flips a coin and survives. B says 1. Limak says 2, flips a coin and loses. B wins.
3
1
Returns: 238095240
The answer is 5/21.
4
4
Returns: 142857144
5
1000000000
Returns: 142857144
2000
123
Returns: 429232785
1987
987654321
Returns: 623410299
3
3
Returns: 333333336
4
1
Returns: 980952388
4
2
Returns: 428571432
4
3
Returns: 977777785
2
1000000000
Returns: 1
3
1000000000
Returns: 142857144
17
71
Returns: 13548253
71
17
Returns: 367271013
2000
1000000000
Returns: 209180237
2000
385428121
Returns: 524769542
2000
900123149
Returns: 867773143
1999
900123149
Returns: 873102228
1876
900123149
Returns: 605689823
1400
900123149
Returns: 7449254
1400
1400000
Returns: 424230633
2000
1
Returns: 220496480
1875
2
Returns: 277116339
1934
900
Returns: 485417411
1345
125486
Returns: 646298747