레이팅 미적용소 캠프에 합격하려면, 베시는 USACOW Open 대회의 마지막 문제에서 좋은 점수를 받아야 한다. 이 문제에는 동일한 가중치를 갖는 \(T\)개의 서로 다른 테스트 케이스(\(2\le T\le 10^3\))가 있으며, 첫 번째 테스트 케이스는 예제 케이스이다. 최종 점수는 마지막 제출이 통과한 테스트 케이스의 수와 같다.
안타깝게도 베시는 너무 피곤해서 문제를 생각할 수가 없지만, 각 테스트 케이스의 정답이 "yes" 아니면 "no"이므로 계획이 있다! 정확히 말하면, 다음과 같은 비결정적 풀이를 반복해서 제출하기로 한다.
if input == sample_input:
print sample_output
else:
print "yes" or "no" each with probability 1/2, independently for each test case
예제를 제외한 모든 테스트 케이스에 대해, 이 프로그램은 다시 제출할 때 다른 출력을 낼 수 있으므로, 통과하는 테스트 케이스의 수는 매번 달라질 수 있다.
베시는 총 \(K\)번(\(1\le K\le 10^9\))을 초과하여 제출할 수 없다는 것을 알고 있다. 그렇게 하면 반드시 실격되기 때문이다. 베시가 최적 전략을 따른다고 할 때, 최종 점수의 기댓값의 최댓값은 얼마인가?
Problem credits: Benjamin Qi
채점 방식
- 테스트 케이스 3-6은 \(T\le 25\)이고 \(K\le 100\)을 만족한다.
- 테스트 케이스 7-9는 \(K\le 10^6\)을 만족한다.
- 테스트 케이스 10-17은 추가 제약이 없다.
Problem credits: Benjamin Qi
입력은 한 줄로 이루어지며, 공백으로 구분된 두 정수 \(T\)와 \(K\)가 주어진다.
실제 답과의 절대 오차 또는 상대 오차가 \(10^{-6}\) 이하인 소수로 답을 출력한다.
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