DotA Quals

Time limit1sMemory limit256 MB

Summary

Given 2^n players and Idned ranked k-th, compute the expected number of rounds he survives when opponents are randomly paired each round and the higher rating always wins.

Level: Medium7 of 10
Topics: Probability, Combinatorics, Math, Dynamic programming
Solved: No attempts yet

Problem

Instead of studying for the coming exams, a student with the nickname "Idned" has decided to enter an open qualification for a huge DotA (Development of the Algorithms) tournament. The qualification is a single-elimination tournament with $2^n$ participants, and Idned is one of them. There are $n$ rounds in total. Before each round, all remaining participants are randomly divided into pairs, with every possible division equally likely. In each pair the two participants play, and the loser quits the tournament and does not play in later rounds.

Every participant has a unique rating, and Idned's rating is the $k$ -th highest. Idned is sure that the outcome of each game is fully determined by the two participants' ratings, with the higher rating winning. Under this assumption, can you determine the expected number of rounds in which Idned takes part?

Input

The input contains two integers $n$ and $k$ : the total number of rounds and Idned's position in the overall rating ( $1 \le n \le 10$ ; $1 \le k \le 2^n$ ).

Output

Output the expected number of rounds.

Your answer must be correct to within an absolute or relative error of $10^{-9}$ . Formally, let your answer be $a$ and the jury's answer be $b$ . Your answer is considered correct if $\frac{|a-b|}{\max(1, |b|)} \le 10^{-9}$ .

Examples2

Example 1
Input
```
2 2
```
Expected output
```
1.666666666667
```
Example 2
Input
```
3 5
```
Expected output
```
1.457142857143
```