Cow Camp
플래티넘 II의견: 0
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\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
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\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?
Problem credits: Benjamin Qi
SCORING
- Test cases 3-6 satisfy \(T\le 25\) and \(K\le 100.\)
- Test cases 7-9 satisfy \(K\le 10^6.\)
- Test cases 10-17 satisfy no additional constraints.
Problem credits: Benjamin Qi
The only line of input contains two space-separated integers \(T\) and \(K.\)
The answer as a decimal that differs by at most \(10^{-6}\) absolute or relative
error from the actual answer.
2 31.875In 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\).
4 22.8750000000000000000Here, Bessie should only submit twice if she passes fewer than \(3\) test cases on
her first try.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > February > Gold
평가 및 의견
Cow Camp
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cow Camp