P8190 [USACO22FEB] Cow Camp G

题目描述

为了获得参加奶牛训练营的资格，Bessie 需要在 USACOW 公开赛的最后一题中取得好成绩。这道题有 $T$ 个独立的测试用例（$2 \leq T \leq 10^3$），权重相同，其中第一个测试用例是样例。她的最终得分将等于她最后一次提交通过的测试用例数量。

不幸的是，Bessie 太累了，无法思考这个问题，但由于每个测试用例的答案要么是“yes”，要么是“no”，她想到了一个计划！具体来说，她决定反复提交以下非确定性解决方案：

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

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

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

输入格式

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

输出格式

输出一个十进制数，表示答案，与实际答案的绝对误差或相对误差不超过 $10^{-6}$。

样例解释 1

在这个例子中，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$ 的概率。

样例解释 2

在这里，Bessie 应该只在第一次尝试通过少于 3 个测试用例时才提交第二次。

输入输出样例 1

2 3

1.875

输入输出样例 2

4 2

2.8750000000000000000

说明/提示

• 测试用例 3-6 满足 $T \leq 25$ 且 $K \leq 100$。
• 测试用例 7-9 满足 $K \leq 10^6$。
• 测试用例 10-17 没有额外限制。