Coin Tournament
Time limit2sMemory limit1024 MB
Given x thieves at positions 1..x and y assassins at x+1..x+y, repeatedly the highest-positioned player challenges the one at floor(k/2); find the probability an assassin wins.
- Level
Medium7 of 10
- Topics
- Probability, Dynamic programming, Math, Recursion
- Solved
- No attempts yet
Problem
The Thieves Guild is holding a coin tossing tournament. A total of thieves and assassins, participants, will take part. Initially each participant stands at a position denoted by an integer from to . Games are played while at least two participants remain. In each game, take the participant standing at the position with the greatest number. Let that position be . Participant tosses a fair coin and tries to move to position , where some participant currently stands. If the coin comes up heads, moves to 's position and is eliminated from the tournament. If it comes up tails, is eliminated and stays at the same position. The last remaining participant is the winner.
The assassins' delegation was late for registration, so the thieves took the positions from to , and the assassins were left with the positions from to . The tournament treasurer wants to know in advance the probability that an assassin wins the tournament, given that every game uses a fair coin, that is, heads and tails each come up with probability and all coin tosses are independent. Find this probability.
Input
The first line contains two integers and : the number of thieves and the number of assassins ().
Output
Output the required probability as a decimal fraction. Your answer is considered correct if the absolute or relative error is less than .