cho.sh

관람차 (큰 입력)

원형 관람차에서 시작 위치가 균일하게 무작위인 방문객들이 빈 곤돌라를 모두 채울 때까지 받는 평균 총요금을 계산합니다.

어려움8확률동적 계획법조합론아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

관람차에는 곤돌라 NN개가 원형으로 달려 있고, 관람차는 천천히 돈다. 곤돌라는 입구를 하나씩 지나가고, 입구에서 기다리던 손님은 지나가는 곤돌라에 탈 수 있다.

곤돌라 하나에는 한 명만 탄다. 입구를 지나는 곤돌라에 이미 사람이 타고 있으면 손님은 다음 곤돌라를 기다리고, 그 곤돌라에도 사람이 있으면 또 그다음 곤돌라를 기다린다. 빈 곤돌라가 올 때까지 이 과정을 되풀이한다. 이 문제에서 곤돌라에서 내리는 사람은 없다. 한 번 탄 사람은 그대로 관람차와 함께 계속 돈다.

요금은 기다린 만큼 달라진다. 입구를 처음 지나는 곤돌라가 비어 있으면 손님은 NN달러를 낸다. 그 곤돌라에 사람이 있어서 두 번째 곤돌라를 기다려야 하면 N−1N-1달러를 낸다. 앞의 두 곤돌라에 사람이 있어서 세 번째 곤돌라에 타면 N−2N-2달러를 낸다. 일반적으로 사람이 타고 있는 곤돌라 KK개를 그냥 보낸 손님은 N−KN-K달러를 낸다. 가장 나쁜 경우에는 하나만 남기고 모든 곤돌라를 보내므로 1달러만 낸다.

손님이 오는 시각은 무작위다. 따라서 각 손님 앞을 처음 지나는 곤돌라는 곤돌라 NN개 중에서 균등하게 정해지고, 손님마다 서로 독립이다. 앞 손님이 아직 타지 못한 동안에는 새 손님이 오지 않으므로 줄은 생기지 않는다. 손님은 언제나 자기 앞을 지나는 첫 번째 빈 곤돌라에 탄다.

곤돌라의 개수와 이미 사람이 타고 있는 곤돌라가 주어진다. 모든 곤돌라가 찰 때까지 받는 요금 총액의 평균을 구하여라.

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다. 다음 TT개의 줄에는 테스트 케이스가 한 줄에 하나씩 주어지며, 각 줄은 '.'(마침표)와 'X'(대문자 X)로만 이루어진다. 이 줄의 길이가 NN이다. ii번째 문자가 'X'이면 ii번 곤돌라에 이미 사람이 타고 있고, '.'이면 아직 비어 있다. 곤돌라 번호는 입구를 지나는 순서를 따른다. 1번 곤돌라 다음에 2번 곤돌라가 오고, 마지막 곤돌라 다음에는 다시 1번 곤돌라가 온다.

  • 1≤T≤501 \le T \le 50
  • 1≤N≤2001 \le N \le 200

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 받는 요금 총액의 평균이다. yy는 소수점 아래 여섯 자리까지 반올림해서 출력한다.

힌트

.X.의 답이 나오는 과정은 다음과 같다. 곤돌라는 세 개이고 2번에 사람이 타고 있으므로 손님 두 명이 오고, 각 손님 앞을 처음 지나는 곤돌라는 세 가지다. 따라서 확률이 각각 1/91/9인 아홉 가지 경우가 나온다.

첫 손님 앞을 1번 곤돌라가 처음 지나가면 그 곤돌라가 비어 있으므로 첫 손님은 3달러를 낸다. 이어서 둘째 손님이 온다.

  • 둘째 손님 앞을 1번 곤돌라가 처음 지나가면 1번과 2번 모두 차 있으므로 3번에 타고 1달러를 낸다. 합계 4달러.
  • 둘째 손님 앞을 2번 곤돌라가 처음 지나가면 2번이 차 있으므로 3번에 타고 2달러를 낸다. 합계 5달러.
  • 둘째 손님 앞을 3번 곤돌라가 처음 지나가면 3번이 비어 있으므로 3달러를 낸다. 합계 6달러.

첫 손님 앞을 2번 곤돌라가 처음 지나가면 2번이 차 있으므로 첫 손님은 3번에 타고 2달러를 낸다. 이어서 둘째 손님이 온다.

  • 둘째 손님 앞을 1번 곤돌라가 처음 지나가면 1번이 비어 있으므로 3달러를 낸다. 합계 5달러.
  • 둘째 손님 앞을 2번 곤돌라가 처음 지나가면 2번과 3번 모두 차 있으므로 1번에 타고 1달러를 낸다. 합계 3달러.
  • 둘째 손님 앞을 3번 곤돌라가 처음 지나가면 3번이 차 있으므로 1번에 타고 2달러를 낸다. 합계 4달러.

첫 손님 앞을 3번 곤돌라가 처음 지나가면 3번이 비어 있으므로 첫 손님은 3달러를 낸다. 이어서 둘째 손님이 온다.

  • 둘째 손님 앞을 1번 곤돌라가 처음 지나가면 1번이 비어 있으므로 3달러를 낸다. 합계 6달러.
  • 둘째 손님 앞을 2번 곤돌라가 처음 지나가면 2번과 3번 모두 차 있으므로 1번에 타고 1달러를 낸다. 합계 4달러.
  • 둘째 손님 앞을 3번 곤돌라가 처음 지나가면 3번이 차 있으므로 1번에 타고 2달러를 낸다. 합계 5달러.

아홉 가지 가운데 3달러를 받는 경우가 하나, 4달러가 셋, 5달러가 셋, 6달러가 둘이므로 평균은 (1×3+3×4+3×5+2×6)/9=42/9=4.666666…(1 \times 3 + 3 \times 4 + 3 \times 5 + 2 \times 6)/9 = 42/9 = 4.666666\ldots달러다.