Hide

Problem D
Kolkrabbaleikarnir

Languages en is
/problems/kolkrabbaleikarnir/file/statement/en/img-0001.jpg
Image from wikimedia.org

The Oktopus Games 2022 have begun. Arnar, also known as Oktopus, invited a number of contestants to participate in this exciting contest, in which the prize is a large sum of cash. The contest includes multiple different games. At the start of the contest, the number of contestants was $1\, 234\, 567$, but after competing in the past four games, many contestants have been eliminated. Therefore only $m$ contestants remain.

It is now time for the fifth game and the contestants have been put in a single queue. The person at the front of the queue is none other than Hlini. He steps into the gameroom and realizes that he stands on a platform. On the other side of the room is another platform, and between the platforms is a long bridge. However, this is no ordinary bridge. The bridge consists of $n$ rows, where each row has two glass tiles. The contestants must cross the glass bridge by picking either glass tile in each row.

The glass tiles look identical, but not everything is as it seems and assuming so may prove fatal. One of the tiles is made of tempered glass and can support the weight of a person. The other tile is made of ordinary glass and will break under the weight of a person. The contestant would then fall down and be eliminated.

After Arnar explains the rules, Hlini exclaims: “This is just fifty-fifty, either I cross or I don’t.” Arnar explains to him that his statement is incorrect, since for each step he takes there is a fifty-fifty chance of him guessing correctly. Each contestant, except for Hlini, has perfect memory. Each contestant has a perfect sense of balance.

There are many members in the audience and a common minigame for them is guessing how many contestants will remain at the end of each game. What is the expected number of contestants after this game?

Input

Input is a single line with two integers $n$, the number of rows in the bridge, and $m$, the number of contestants in the game, where $0 \leq n \leq 10^6$ and $0 \leq m \leq 10^6$.

Output

Your output should consist of a single line with a single real number, the expected number of contestants at the end of the game. The output should have an absolute or relative error of at most $10^{-6}$.

Scoring

Group

Points

Constraints

1

10

The bridge has one row.

2

20

Hlini is the only remaining contestant.

3

30

$0 \leq n, m \leq 10$

4

30

$0 \leq n, m, \leq 1000$

5

10

No further constraints.

Sample Input 1 Sample Output 1
2 2
1
Sample Input 2 Sample Output 2
1 5
4.5
Sample Input 3 Sample Output 3
3 1
0.125

Please log in to submit a solution to this problem

Log in