Cow Camp Final Problem

To qualify for cow camp, Bessie must maximize her score on the last problem of the USACOW Open contest. The problem consists of \(T\) distinct test cases (\(2 \le T \le 10^3\)), each weighted equally, where the first test case is the sample.

For non-sample test cases, the answer is either yes or no. Bessie uses a nondeterministic solution that works as follows:

if input == sample_input:
  print sample_output
else:
  print "yes" or "no" each with probability \(\frac{1}{2}\) independently

Since all non-sample test cases are answered at random, the number of correctly answered cases in one submission follows a binomial distribution \(\text{Binomial}(T-1, \frac{1}{2})\). Note that the sample test case is always solved correctly, so every submission guarantees a baseline score of 1.

Bessie is allowed at most \(K\) submissions (\(1 \le K \le 10^9\)). By observing the outcomes, she can employ an optimal stopping strategy to select the final submission. If we define a random variable \(X\) as the number of correct answers in non‐sample cases, her final score is \(1+X\).

More formally, let \(F(m)=\sum_{j=0}^{m}\frac{\binom{T-1}{j}}{2^{T-1}}\) be the cumulative distribution function of \(\text{Binomial}(T-1, \frac{1}{2})\). Over \(K\) independent submissions, if we let \(M\) be the maximum value of \(X\), then the expected maximum is given by:

[ E[M] = \sum_{m=0}^{T-1} \Big(1 - \Big(F(m)\Big)^K\Big), ]

and thus, the maximum expected final score is:

[ E[\text{score}] = 1 + E[M]. ]

Your task is to compute this maximum expected final score. Output the result with at least 6 decimal places of precision.

inputFormat

The input consists of a single line containing two integers, (T) and (K):

• (T): the total number of distinct test cases (including the sample case).
• (K): the maximum number of submissions allowed.

outputFormat

Output a single number, which is the maximum expected final score (accurate to at least 6 decimal places).

sample

2 1

1.500000