This page is still under construction.

Parts of this page are still being built. What you see may change.

Coin Tournament

Time limit2sMemory limit1024 MB

Summary
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 xx thieves and yy assassins, x+yx + y participants, will take part. Initially each participant stands at a position denoted by an integer from 11 to x+yx + y. Games are played while at least two participants remain. In each game, take the participant AA standing at the position with the greatest number. Let that position be kk. Participant AA tosses a fair coin and tries to move to position ⌊k/2⌋\lfloor k / 2 \rfloor, where some participant BB currently stands. If the coin comes up heads, AA moves to BB's position and BB is eliminated from the tournament. If it comes up tails, AA is eliminated and BB 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 11 to xx, and the assassins were left with the positions from x+1x + 1 to x+yx + y. 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 1/21 / 2 and all coin tosses are independent. Find this probability.

Input

The first line contains two integers xx and yy: the number of thieves and the number of assassins (1≤x,y≤1 000 0001 \le x, y \le 1\,000\,000).

Output

Output the required probability as a decimal fraction. Your answer is considered correct if the absolute or relative error is less than 10−610^{-6}.

Examples2

  1. Example 1

    Input
    1 1
    
    Expected output
    0.5
    
  2. Example 2

    Input
    5 3
    
    Expected output
    0.312500000000