## USACO 2022 February Contest, Gold

## Problem 2. Cow Camp

Contest has ended.

**Log in to allow submissions in analysis mode**

Unfortunately, Bessie is way too tired to think about the problem, but since the answer to each test case is either "yes" or "no," she has a plan! Precisely, 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 all test cases besides the sample, this program may produce a different output when resubmitted, so the number of test cases that it passes will vary.

Bessie knows that she cannot submit more than $K$ ($1\le K\le 10^9$) times in total because then she will certainly be disqualified. What is the maximum possible expected value of Bessie's final score, assuming that she follows the optimal strategy?

#### INPUT FORMAT (input arrives from the terminal / stdin):

The only line of input contains two space-separated integers $T$ and $K.$#### OUTPUT FORMAT (print output to the terminal / stdout):

The answer as a decimal that differs by at most $10^{-6}$ absolute or relative error from the actual answer.#### SAMPLE INPUT:

2 3

#### SAMPLE OUTPUT:

1.875

In this example, Bessie should keep resubmitting until she has reached $3$ submissions or she receives full credit. Bessie will receive full credit with probability $\frac{7}{8}$ and half credit with probability $\frac{1}{8}$, so the expected value of Bessie's final score under this strategy is $\frac{7}{8}\cdot 2+\frac{1}{8}\cdot 1=\frac{15}{8}=1.875$. As we see from this formula, the expected value of Bessie's score can be calculated by taking the sum over $x$ of $p(x) \cdot x$, where $p(x)$ is the probability of receiving a score of $x$.

#### SAMPLE INPUT:

4 2

#### SAMPLE OUTPUT:

2.8750000000000000000

Here, Bessie should only submit twice if she passes fewer than $3$ test cases on her first try.

#### SCORING

- Test cases 3-6 satisfy $T\le 25$ and $K\le 100.$
- Test cases 7-9 satisfy $K\le 10^6.$
- Test cases 10-17 satisfy no additional constraints.

Problem credits: Benjamin Qi