Problem 2. Cow Camp

USACO 2022 February Contest, Gold

要获得参加奶牛训练营的资格，Bessie 需要在 USACOW Open 的最后一道题上得到高分。这道题目有 $T$ 个不同而分值相等的测试点（$2\le T\le 10^3$），其中第一个测试点是样例。她的最终分数将等于她最后一次提交所通过的测试点的数量。

不幸的是，Bessie 已经累到难以思考这道题目，但由于每个测试点的答案都是「是」或「否」，她就有了一个计划！准确地说，她决定反复提交以下非确定性的程序：

if 输入 == 输入样例:
  输出 输出样例
else:
  对于每个测试点独立地，以各 1/2 的概率输出「是」或「否」

注意对于除样例之外的所有测试点，此程序在重新提交时可能会产生不同的输出，因此它通过的测试点的数量可能会不同。

Bessie 知道她总共提交的次数不能超过 $K$（$1\le K\le 10^9$）次，否则她肯定会被取消资格。假设 Bessie 遵循最优策略，她最终得分的最大可能期望值是多少？

输入格式（从终端 / 标准输入读入）：

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

输出格式（输出至终端 / 标准输出）：

以小数格式输出答案，与标准答案的绝对或相对误差不超过 $10^{-6}$ 均正确。

输入样例：

2 3

输出样例：

1.875

在这个例子中，Bessie 应持续重新提交，直到她提交满 $3$ 次或获得满分。Bessie 有 $\frac{7}{8}$ 的概率获得满分，$\frac{1}{8}$ 的概率获得一半分数，因此 Bessie 在此策略下最终得分的期望值为 $\frac{7}{8}\cdot 2+\frac{1}{8}\cdot 1=\frac{15}{8}=1.875$。正如我们在这个公式中看到的，Bessie 得分的期望值可以通过对所有 $x$ 的 $p(x)\cdot x$ 求和来计算，其中 $p(x)$ 是获得分数 $x$ 的概率。

输入样例：

4 2

输出样例：:

2.8750000000000000000

在这里，Bessie 应当仅在首次提交通过少于 $3$ 个测试点的情况下提交两次。

测试点性质： 测试点 3-6 满足 $T\le 25$ 以及 $K\le 100$。测试点 7-9 满足 $K\le 10^6$。测试点 10-17 没有额外限制。

供题：Benjamin Qi