카우 캠프에 참가하려면 Bessie가 USACOW Open의 마지막 질문에서 높은 점수를 받아야 합니다. 이 질문에는 T개의 서로 다른 동일한 테스트 포인트(2≤T≤10³)가 있습니다. 여기서 첫 번째 테스트 포인트는 예시입니다. 그녀의 최종 점수는 마지막 제출물에서 통과한 테스트 점수와 동일합니다.

불행히도, 베시는 이 질문에 대해 생각하기에는 너무 피곤하지만 모든 테스트 포인트에 대한 대답이 "예" 또는 "아니오"이기 때문에 그녀는 계획이 있습니다! 정확히 그녀는 다음과 같은 비결정적 절차를 반복적으로 제출하기로 결정했습니다.

입력 == 입력 예:

출력 출력 샘플

또 다른:

각 테스트 포인트에 대해 각각 1/2의 확률로 "예" 또는 "아니오"를 출력합니다.

이 프로그램은 샘플을 제외한 모든 테스트 포인트에 대해 다시 제출할 때 다른 출력을 생성할 수 있으므로 다른 테스트 포인트 수를 통과할 수 있습니다.

Bessie는 총 K(1≤K≤10⁹)번 이상 제출할 수 없다는 것을 알고 있습니다. 그렇지 않으면 반드시 실격됩니다. Bessie가 최적의 정책을 따른다고 가정할 때 최종 점수의 가능한 최대 기대값은 얼마입니까?

#5325 upload 7 done - how_to_reg - auto_awesome 特殊评测

소 캠프 (Cow Camp) timer 2s memory 1024MB

#5325
特殊评测

소 캠프 (Cow Camp) 2s 1024MB