ICPC PACNW 2016 K - Tournament Wins

View as PDF

Submit solution


Points: 12
Time limit: 0.6s
Memory limit: 256M

Problem type

You are one of the 2^k competitors invited to enter a single elimination tournament. You are ranked rth in the published rankings. Furthermore, you know that in any match between two players, the one ranked higher will always win.

The only source of uncertainty is the bracket. If every possible tournament bracket is equally likely, determine your expected number of wins in the tournament. Your expected number of wins is the average number of your wins over all possible tournament bracket orderings.

Input

The input consists of a single line containing the two space-separated integers k (1 \le k \le 20) and r (1 \le r \le 2^k).

Output

Print, on a single line, your expected number of wins in the tournament, rounded and displayed to exactly five decimal places. The sixth digit after the decimal point of the exact answer will never be 4 or 5 (eliminating complex rounding considerations).

Be careful about very small or very large numbers during intermediate steps.

Sample Input 1

3 3

Sample Output 1

1.00000

Sample Input 2

20 130

Sample Output 2

11.65203
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments

There are no comments at the moment.