题目描述

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≤T≤10^3)$ weighted equally, with the first test case being the sample case. Her final score will equal the number of test cases that her last submission passes. 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≤K≤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?

输入格式

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

输出格式

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

题目大意

[USACO22FEB] Cow Camp G

题目描述

为了有资格参加奶牛夏令营，贝西需要在USACOW公开赛的最后一道题上取得好成绩。这个问题有$T$个不同的测试点，这些测试点范围在$（2≤T≤10^3）$，第一个测试点为样本用例。她的最终分数将等于她上一次提交通过的测试点数。

但是，贝西太累了，无法思考这个问题，由于每个测试点的答案要么是“yes”，要么是“no”，她有一个计划！确切地说，她决定反复提交以下不确定的解决方案：

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

但请注意，对于除示例之外的所有测试点，重新提交时，此程序可能会产生不同的输出，因此它通过的测试用例数量会有所不同。 贝西知道她提交的样例不能超过$K （1≤K≤10^9）$次，因为那样她肯定会被取消资格。假设贝西遵循最佳策略，她最终得分的最大可能期望值是多少？

输入格式

第一行输入包含两个空格分隔的整数$T$和$K$

输出格式

答案为小数，最多相差$10^{−6}$。

提示

【样例解释 1】

在样例中，贝西应继续重新提交，直到她提交了3份意见书或获得全额学分。贝西将获得概率为$\frac 78$的全学分和概率为$\frac 18$的半学分，因此贝西在该策略下的最终得分预期值为$\frac 78\cdot 2+\frac 18\cdot 1=\frac{15}{8}=1.875$。正如我们从这个公式中看到的，贝西分数的期望值可以通过取$p（x）\cdot x$中超过$x$的总和来计算，其中$p（x）$是获得$x$分数的概率。

【样例解释 2】

在这个样例中，如果贝西第一次通过的测试用例少于3个，她应该只提交两次。

【数据范围】

• 测试样例3-6满足$T≤25$和$K≤100$

• 测试样例7-9满足$K≤10^6$

• 测试样例10-17不满足其他约束.

2 3

1.875

4 2

2.8750000000000000000

提示

【样例解释 1】

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 78$ and half credit with probability $\frac 18$, so the expected value of Bessie's final score under this strategy is $\frac 78\cdot 2+\frac 18\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$.

【样例解释 2】

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

【数据范围】

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