Cow Camp

题目描述

为了获得奶牛夏令营的资格，Bessie 需要在 USACOW Open 比赛的最后一题中取得好成绩。本题共有 $T$ 个互不相同的测试点（$2\le T\le 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\le K\le 10^9$），否则一定会被取消资格。假设她采取最优策略，Bessie 最终得分的期望值最大可能是多少？

输入格式

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

输出格式

输出一个十进制数，使其与真实答案的绝对或相对误差至多为 $10^{-6}$。

2 3

1.875

4 2

2.8750000000000000000

提示

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

这里，如果她第一次尝试通过的测试点少于 $3$ 个，Bessie 才应该只提交两次。

计分 测试点 3-6 满足 $T\le 25$ 且 $K\le 100.$ 测试点 7-9 满足 $K\le 10^6.$ 测试点 10-17 无额外限制。 题目作者：Benjamin Qi

标签: USACO|2022|Gold

来源

USACO|2022|Gold