P6968: 奶牛营地
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
要获得参加奶牛训练营的资格,Bessie
需要在 USACOW Open 的最后一道题上得到高分。这道题目有 T
个不同而分值相等的测试点(2≤T≤10^3
),其中第一个测试点是样例。她的最终分数将等于她最后一次提交所通过的测试点的数量。
不幸的是,Bessie
已经累到难以思考这道题目,但由于每个测试点的答案都是「是」或「否」,她就有了一个计划!准确地说,她决定反复提交以下非确定性的程序:
if
输入 == 输入样例:
输出 输出样例
else:
对于每个测试点独立地,以各 1/2
的概率输出「是」或「否」
注意对于除样例之外的所有测试点,此程序在重新提交时可能会产生不同的输出,因此它通过的测试点的数量可能会不同。
Bessie
知道她总共提交的次数不能超过 K(1≤K≤10
^9
)次,否则她肯定会被取消资格。假设 Bessie
遵循最优策略,她最终得分的最大可能期望值是多少?
【
输入格式】
(从终端 /
标准输入读入):
输入一行,包含两个空格分隔的整数 T
和 K。
【
输出格式】
(输出至终端 /
标准输出):
以小数格式输出答案,与标准答案的绝对或相对误差不超过 10
^−6
均正确。
【
输入样例】
:
2 3
【
输出样例】
:
1.875
【样例说明】
在这个例子中,Bessie
应持续重新提交,直到她提交满 3
次或获得满分。Bessie 有 7/8 的概率获得满分,1
/8
的概率获得一半分数,因此 Bessie 在此策略下最终得分的期望值为 7
/8×2+1
/8×1=15
/8=1.875
。正如我们在这个公式中看到的,Bessie 得分的期望值可以通过对所有 x 的 p(x)×x
求和来计算,其中p(x) 是获得分数 x
的概率。
【
输入样例】
:
4 2
【
输出样例】
:
2.8750000000000000000
【样例说明】
在这里,Bessie
应当仅在首次提交通过少于 3 个测试点的情况下提交两次。
【
测试点性质】
:
测试点 3-6
满足T≤25 以及 K≤100。
测试点 7-9
满足 K≤10^6
。
测试点 10-17
没有额外限制。
供题:Benjamin Qi