관람차 | cho.sh

문제

관람차에는 원을 따라 놓인 곤돌라가 $N$ 개 있고, 관람차는 천천히 돈다. 곤돌라는 하나씩 차례로 입구를 지나가며, 곤돌라가 입구를 지날 때 입구에 서 있던 사람이 그 곤돌라에 탈 수 있다.

이 문제의 곤돌라는 작아서 한 대에 한 명만 탄다. 입구를 지나는 곤돌라에 이미 사람이 타고 있으면 기다리던 사람은 다음 곤돌라를 기다린다. 그 곤돌라에도 사람이 있으면 또 그다음 곤돌라를 기다리고, 빈 곤돌라가 올 때까지 이렇게 기다린다. 여기서 곤돌라에서 내리는 사람은 생각하지 않는다. 사람은 타기만 하고, 그 뒤로는 충분히 오랫동안 관람차와 함께 돈다고 하자.

기다리는 시간이 길어서 손님이 실망하지 않도록 요금을 이렇게 정했다. 어떤 사람이 관람차에 왔을 때 입구를 처음으로 지나는 곤돌라가 비어 있으면 그 사람은 $N$ 달러를 낸다. 첫 곤돌라에 사람이 있어서 두 번째 곤돌라를 기다려야 하면 $N-1$ 달러를 낸다. 앞의 두 대에 모두 사람이 있어서 세 번째를 기다려야 하면 $N-2$ 달러를 낸다. 일반적으로 사람이 탄 곤돌라 $K$ 대를 그냥 보내고 타는 사람은 $N-K$ 달러를 낸다. 가장 나쁜 경우에는 한 대만 남기고 모두 보내야 하므로 1달러만 낸다.

사람들은 아무 때나 관람차에 온다고 하자. 즉 각 사람마다 입구를 처음으로 지나는 곤돌라는 앞의 상황과 무관하게 균등한 확률로 정해진다. 또 이미 기다리는 사람이 있는 동안에는 아무도 오지 않는다고 하자. 줄이 생기는 상황은 생각하지 않아도 된다. 사람은 언제나 입구를 지나는 빈 곤돌라 중 가장 먼저 오는 곤돌라에 탄다.

곤돌라의 개수와 이미 사람이 탄 곤돌라가 주어진다. 모든 곤돌라가 찰 때까지 벌어들이는 금액의 기댓값을 구하라.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 다음 $T$ 개 줄에 테스트 케이스가 한 줄씩 주어지며, 각 줄은 '.'과 'X'로만 이루어져 있다. 이 줄의 길이가 $N$ 이다. $i$ 번째 문자가 'X'이면 $i$ 번 곤돌라에 이미 사람이 타고 있고, '.'이면 아직 비어 있다. 곤돌라에는 입구를 지나는 순서대로 번호가 붙어 있다. 1번 다음에 2번이 지나고, 마지막 곤돌라가 지나면 다시 1번부터 시작한다.

제한

$1 \le T \le 50$
$1 \le N \le 20$

출력

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 벌어들이는 금액의 기댓값이며 단위는 달러이다. y는 소수점 아래 아홉째 자리까지 반올림하고, 끝자리가 0이어도 아홉 자리를 모두 적는다.

힌트

곤돌라가 세 대이고 두 번째 곤돌라에만 사람이 타고 있는 경우를 보자. 확률이 각각 1/9인 아홉 가지 경우가 있다.

첫 번째 사람이 온다. 입구를 다음으로 지나는 곤돌라가

비어 있는 1번이면 그 사람이 타고 3달러를 낸다. 얼마 뒤 두 번째 사람이 온다. 입구를 다음으로 지나는 곤돌라가
- 사람이 탄 1번이면 2번에도 사람이 있으므로 3번까지 기다려 1달러만 내고 탄다. 모두 4달러를 벌었다.
- 사람이 탄 2번이면 그냥 보내고 3번에 타면서 2달러를 낸다. 모두 5달러를 벌었다.
- 비어 있는 3번이면 3달러를 낸다. 모두 6달러를 벌었다.
사람이 탄 2번이면 첫 번째 사람은 그냥 보내고 3번에 타면서 2달러를 낸다. 얼마 뒤 두 번째 사람이 온다. 입구를 다음으로 지나는 곤돌라가
- 비어 있는 1번이면 3달러를 낸다. 모두 5달러를 벌었다.
- 사람이 탄 2번이면 3번에도 사람이 있으므로 1번까지 기다려 1달러만 내고 탄다. 모두 3달러를 벌었다.
- 사람이 탄 3번이면 그냥 보내고 1번에 타면서 2달러를 낸다. 모두 4달러를 벌었다.
비어 있는 3번이면 첫 번째 사람이 타고 3달러를 낸다. 얼마 뒤 두 번째 사람이 온다. 입구를 다음으로 지나는 곤돌라가
- 비어 있는 1번이면 3달러를 낸다. 모두 6달러를 벌었다.
- 사람이 탄 2번이면 3번에도 사람이 있으므로 1번까지 기다려 1달러만 내고 탄다. 모두 4달러를 벌었다.
- 사람이 탄 3번이면 그냥 보내고 1번에 타면서 2달러를 낸다. 모두 5달러를 벌었다.

아홉 가지 중에서 3달러를 버는 경우가 한 번, 4달러가 세 번, 5달러가 세 번, 6달러가 두 번이므로 기댓값은 $(1 \times 3 + 3 \times 4 + 3 \times 5 + 2 \times 6)/9 = 42/9 = 4.666666666\ldots$ 달러이고, 4.666666667로 출력한다.