증가 수열 카드 게임
시간 제한20초메모리 제한1024 MB
1부터 N까지 적힌 카드를 섞은 더미를 훑으며 마지막으로 가져온 카드보다 큰 수일 때만 가져갈 때, 손에 남는 카드 수의 기댓값을 N마다 구한다.
문제
혼자서 카드 게임을 한다.
카드가 N장 있고, i번째 카드에는 정수 i가 적혀 있다.
먼저 N장의 카드를 무작위로 섞어 더미로 만든다. 더미 맨 위의 카드를 손에 든다. 그런 다음 더미가 빌 때까지 다음 과정을 반복한다.
- 더미 맨 위의 카드를 확인한다.
- 카드에 적힌 수가 마지막으로 든 카드에 적힌 수보다 크면 그 카드를 든다.
- 그렇지 않으면 그 카드를 버린다.
게임의 점수는 마지막에 손에 들고 있는 카드의 수이다. 주어진 카드 수 N에 대해 게임의 기댓값 점수는 얼마인가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄에는 더미에 있는 카드의 수 N이 하나의 정수로 주어진다.
출력
각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 게임이 끝났을 때의 기댓값 점수이다.
y는 정답과의 절대 오차 또는 상대 오차가 10-6 이내이면 정답으로 인정된다.
제한
- 1 ≤ T ≤ 100.