시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

K개의 창문으로 둘러싸인 방이 있다. 창문들은 돌을 맞으면 깨지는데, 창문 중 일부는 강화가 되어 있어 H개의 창문은 첫 번째 돌에는 견디고 두 번째 돌에 깨지며, 나머지는 강화가 되어 있지 않아 첫 번째 돌에 깨진다.

N 명의 악당들이 이 방에서 모임을 가지기로 하였고, 이 모임에서 기념으로 각자 하나씩 창문을 선택해 돌을 하나씩 던지기로 하였다. 이 때 각자 어떤 창문에 던질지 결정하는 것은 다른 사람들의 선택에 무관하며, 이미 깨진 창문에 돌을 던질 경우 돌은 그대로 창문을 통과하게 된다..

 

기본 상태의 창문은 돌 하나나 두 개에 깨지기 때문에, 방의 주인인 당신은 창문들을 강화하기로 결정했다. 그래서 당신은 M 명의 일꾼들을 시켜서 모임 전에 창문을 더 강화하기로 하였다. 각 일꾼도 임의의 창문 하나를 강화하는데, 악당들의 결정과 마찬가지로 각자 어떤 창문을 강화하는지 결정하는 것은 다른 사람들의 결정에 무관하다. 창문을 한 번 강화할 때마다 그 창문은 돌을 한번 더 맞는 것을 견딜 수 있게 된다.

모임 후에 최소한 한 개 이상의 창문이 깨져있을 확률은 얼마일까?

입력

입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다. 각 테스트 케이스는 다음과 같이 네 개의 정수로 주어진다.

K N M H

제한

  • 모든 수들은 자연수이다.
  • 1 ≤ T ≤ 100.
  • 1 ≤ T ≤ 100.
  • 1 ≤ K ≤ 20.
  • 1 ≤ N ≤ 30.
  • 1 ≤ M ≤ 30.
  • 0 ≤ H ≤ K.

출력

각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 한 개 이상의 창문이 깨질 확률이다. 10-6범위의 절대/상대오차는 정답으로 간주된다.

예제 입력 1

3
3 1 1 0
3 2 1 0
3 1 2 2

예제 출력 1

Case #1: 0.66666667
Case #2: 1.00000000
Case #3: 0.14814815

힌트

모든 예제의 방에는 3개의 창문이 있다.
1번 예제의 경우, 강화한 창문과 돌을 맞은 창문이 같은 경우에만 창문이 깨지지 않으므로, 창문이 깨질 확률은 2/3이다.
2번 예제의 경우, 어떤 창문이 강화되고, 돌 하나가 그 창문을 때려서 버텼다고 하더라도, 어떤 창문이라도 두번째 돌을 버틸 수 없으므로, 창문이 깨질 확률은 1이다.
3번 예제의 경우, 두 개의 강화 창문은 깨질 염려가 없다. 다만, 남은 창문 하나가 어느 일꾼에 의해서도 강화되지 않고 돌을 맞았을 경우에는 창문이 깨지므로, 전체적으로 창문이 깨지는 확률은 2/3*2/3*1/3 = 4/27이다.