#PU1210. USACO 2022 February Contest, Gold — Problem 2. Cow Camp

    ID: 1335 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb22来源:usaco.orgscoring:equal_test_cases概率期望

USACO 2022 February Contest, Gold — Problem 2. Cow Camp

USACO 2022 February Contest, Gold — Problem 2. Cow Camp

题目描述

To qualify for cow camp, Bessie needs to earn a good score on the last problem of the USACOW Open contest. This problem has TT distinct test cases (2≤T≤1032\le T\le 10^3) weighted equally, with the first test case being the sample case. Her final score will equal the number of test cases that her last submission passes. Unfortunately, Bessie is way too tired to think about the problem, but since the answer to each test case is either "yes" or "no," she has a plan! Precisely, she decides to repeatedly submit the following nondeterministic solution: if input == sample_input: print sample_output else: print "yes" or "no" each with probability 1/2, independently for each test case

输入格式

The only line of input contains two space-separated integers TT and K.K.

输出格式

The answer as a decimal that differs by at most 10−610^{-6} absolute or relative error from the actual answer.

数据范围

Test cases 3-6 satisfy T≤25T\le 25 and K≤100.K\le 100. Test cases 7-9 satisfy K≤106.K\le 10^6. Test cases 10-17 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 1

2 3
1.875
In this example, Bessie should keep resubmitting until she has reached $3$
submissions or she  receives full credit. Bessie will receive full credit with
probability $\frac{7}{8}$ and half credit with probability $\frac{1}{8}$, so the
expected value of Bessie's  final score under this strategy is
$\frac{7}{8}\cdot 2+\frac{1}{8}\cdot 1=\frac{15}{8}=1.875$.  As we see from this
formula, the expected value of Bessie's score can be calculated by  taking the
sum over $x$ of $p(x) \cdot x$, where $p(x)$ is the probability of receiving a
score of
$x$.

样例 2

4 2
2.8750000000000000000
Here, Bessie should only submit twice if she passes fewer than $3$ test cases on
her first try.

提示

different output when resubmitted, so the number of test cases that it passes will vary. Bessie knows that she cannot submit more than KK (1≤K≤1091\le K\le 10^9) times in total because then she will certainly be disqualified. What is the maximum possible expected value of Bessie's final score, assuming that she follows the optimal strategy?