P8190 [USACO22FEB] Cow Camp G

To qualify for cow camp, Bessie needs to earn a good score on the last problem of the USACOW Open contest. This problem has $T$ distinct test cases $(2≤T≤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 ``` Note that for all test cases besides the sample, this program may produce a different output when resubmitted, so the number of test cases that it passes will vary. Bessie knows that she cannot submit more than $K$ $(1≤K≤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?

N/A

N/A

【样例解释 1】 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 78$ and half credit with probability $\frac 18$, so the expected value of Bessie's final score under this strategy is $\frac 78\cdot 2+\frac 18\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】 Here, Bessie should only submit twice if she passes fewer than 3 test cases on her first try. 【数据范围】 - Test cases 3-6 satisfy $T≤25$ and $K≤100$. - Test cases 7-9 satisfy $K≤10^6$. - Test cases 10-17 satisfy no additional constraints.