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 遵循最优策略，她的最终得分的最大可能期望值是多少？

无

无

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