문제
카우 캠프에 참가하려면 Bessie가 USACOW Open의 마지막 질문에서 높은 점수를 받아야 합니다. 이 질문에는 T개의 서로 다른 동일한 테스트 포인트(2≤T≤103)가 있습니다. 여기서 첫 번째 테스트 포인트는 예시입니다. 그녀의 최종 점수는 마지막 제출물에서 통과한 테스트 점수와 동일합니다.
불행히도, 베시는 이 질문에 대해 생각하기에는 너무 피곤하지만 모든 테스트 포인트에 대한 대답이 "예" 또는 "아니오"이기 때문에 그녀는 계획이 있습니다! 정확히 그녀는 다음과 같은 비결정적 절차를 반복적으로 제출하기로 결정했습니다.
입력 == 입력 예:
출력 출력 샘플
또 다른:
각 테스트 포인트에 대해 각각 1/2의 확률로 "예" 또는 "아니오"를 출력합니다.
이 프로그램은 샘플을 제외한 모든 테스트 포인트에 대해 다시 제출할 때 다른 출력을 생성할 수 있으므로 다른 테스트 포인트 수를 통과할 수 있습니다.
Bessie는 총 K(1≤K≤109)번 이상 제출할 수 없다는 것을 알고 있습니다. 그렇지 않으면 반드시 실격됩니다. Bessie가 최적의 정책을 따른다고 가정할 때 최종 점수의 가능한 최대 기대값은 얼마입니까?
입력
공백으로 구분된 두 개의 정수 T와 K를 포함하는 행을 입력하십시오.
출력
10진수 형식으로 답을 출력하며, 이는 표준 답의 절대오차 또는 상대오차 10−6 이내입니다.
예제1
입력
2 3
출력
1.875
예제2
입력
4 2
출력
2.8750000000000000000
힌트
출처
USACO 2022 February Gold