카우 캠프

시간 제한2초메모리 제한1024 MB

요약

샘플 테스트는 항상 통과하고 나머지 T-1개는 무작위로 찍는 제출을 최대 K번 하면서 언제 멈출지 최적으로 정할 때 기대 점수의 최댓값을 구합니다.

난이도: 어려움10점 중 8점
유형: 확률, 동적 계획법, 수학
정답자: 아직 제출이 없습니다

문제

카우 캠프에 참가할 자격을 얻으려면 Bessie가 USACOW Open 대회의 마지막 문제에서 좋은 점수를 받아야 한다. 이 문제에는 같은 배점의 서로 다른 테스트 케이스가 $T$ 개 있으며( $2\le T\le 10^3$ ), 첫 번째 테스트 케이스는 예제 케이스이다. Bessie의 최종 점수는 마지막 제출이 통과한 테스트 케이스의 수와 같다.

안타깝게도 Bessie는 너무 피곤해서 문제를 생각할 수 없지만, 각 테스트 케이스의 답이 "yes" 또는 "no"이므로 계획이 하나 있다. 정확히는 다음 비결정적 풀이를 반복해서 제출하기로 한다.

if input == sample_input:
  print sample_output
else:
  print "yes" or "no" each with probability 1/2, independently for each test case

예제 외의 모든 테스트 케이스에서 이 프로그램은 다시 제출할 때 다른 출력을 낼 수 있으므로, 통과하는 테스트 케이스의 수가 달라질 수 있다.

Bessie는 총 $K$ 번( $1\le K\le 10^9$ )을 초과해 제출하면 반드시 실격되므로, 제출 횟수가 $K$ 번을 넘을 수 없다는 것을 알고 있다. Bessie가 최적의 전략을 따른다고 할 때, 최종 점수의 기댓값으로 가능한 최댓값은 얼마인가?

입력

입력은 한 줄로 주어지며, 공백으로 구분된 두 정수 $T$ 와 $K$ 가 포함된다.

출력

실제 정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하가 되도록 소수로 출력한다.

예제2

예제 1
입력
```
2 3
```
예상 출력
```
1.875
```
예제 2
입력
```
4 2
```
예상 출력
```
2.8750000000000000000
```