Flipping Coins

Time limit4sMemory limit512 MB

Summary

Given N coins all tails and exactly K fair tosses chosen adaptively, find the maximum expected number of heads at the end.

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

Problem

Line up $N$ identical coins in a row. Every coin starts tails up. Exactly $K$ times you pick one coin, toss it into the air and put it back where it was. The coin lands heads up with probability $1/2$ and tails up with probability $1/2$ . Once all $K$ tosses are done, you keep every coin that is heads up.

You choose which coin to toss right before each toss, after seeing all the results so far. All $K$ tosses must happen, and you cannot stop early even when every coin is already heads up.

Find the expected number of coins you keep when you choose the coins so that this expectation is as large as possible.

Input

One line with two space separated integers $N$ and $K$ . $N$ is the number of coins ( $1 \le N \le 400$ ) and $K$ is the number of tosses you must perform ( $1 \le K \le 400$ ).

Output

Print the largest expected number of coins that are heads up at the end, rounded to six decimal places, on one line. Print all six digits after the decimal point, and round an exact halfway value upward.

Examples5

Example 1
Input
```
2 1
```
Expected output
```
0.500000
```
Example 2
Input
```
2 2
```
Expected output
```
1.000000
```
Example 3
Input
```
2 3
```
Expected output
```
1.250000
```
Example 4
Input
```
6 10
```
Expected output
```
4.634766
```
Example 5
Input
```
6 300
```
Expected output
```
5.500000
```