Cow Camp

Time limit2sMemory limit1024 MB

Summary

With up to K submissions that always pass the sample and guess the other T-1 cases fairly, find the maximum expected final score under optimal stopping.

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

Problem

To qualify for cow camp, Bessie needs to earn a good score on the last problem of the USACOW Open contest. This problem has $T$ distinct test cases ( $2\le T\le 10^3$ ) weighted equally, and the first test case is the sample case. Her final score equals the number of test cases that her last submission passes.

Unfortunately, Bessie is too tired to think about the problem, but since the answer to each test case is either "yes" or "no," she has a plan. Specifically, she decides to repeatedly submit the following nondeterministic solution:

if input == sample_input:
  print sample_output
else:
  print "yes" or "no" each with probability 1/2, independently for each test case

Note that for every test case other than the sample, this program may produce a different output when resubmitted, so the number of test cases it passes can vary.

Bessie knows that she cannot submit more than $K$ times in total ( $1\le K\le 10^9$ ), since doing so will certainly disqualify her. Assuming Bessie follows an optimal strategy, what is the maximum possible expected value of her final score?

Input

The only line of input contains two space-separated integers $T$ and $K$ .

Output

Print a decimal that differs from the actual answer by at most $10^{-6}$ absolute or relative error.

Examples2

Example 1
Input
```
2 3
```
Expected output
```
1.875
```
Example 2
Input
```
4 2
```
Expected output
```
2.8750000000000000000
```