BearCircleGame
2016 TCO Algo Parallel 2C · 2016-03-24 · by Errichto
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
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.
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
Submissions are judged against all 27 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BearCircleGame with a public method int winProbability(int n, int k) · 27 test cases · 2 s / 256 MB per case