ARAM (큰 데이터)

League of Legends™에는 ARAM이라는 게임 모드가 있다. All Random, All Mid의 약자다. 이 문제는 그 규칙을 단순하게 바꾼 것이므로 게임을 해 본 적이 없어도 풀 수 있다.

ARAM 한 판을 시작할 때마다 $N$명의 챔피언 중 한 명이 균등한 확률로 배정된다. 챔피언마다 이길 확률이 달라서 운이 나쁘면 다른 챔피언을 받고 싶어진다. 게임에는 리롤 기능이 있다.

리롤 권한은 돈처럼 쓴다. 첫 판을 시작하기 전에 $R$ RD(리롤 달러)를 가지고 시작한다. RD가 $1$ 이상일 때만 리롤할 수 있고 리롤 한 번에 $1$ RD를 쓴다. 한 판이 끝나면 $1/G$ RD를 얻지만 ($G$는 정수) RD는 $R$을 넘지 못한다. $R$ RD를 가진 채로 한 판을 더 하면 그 판이 끝나도 RD는 그대로 $R$이다.

RD가 $1$ 이상일 때 리롤을 고르면 $1$ RD를 쓰고 $N$명 중 한 명을 균등한 확률로 다시 배정받는다. 처음과 같은 챔피언이 나올 수도 있다. 리롤로 받은 챔피언도 마음에 들지 않고 RD가 아직 $1$ 이상 남아 있으면 다시 리롤할 수 있다. RD가 $1$ 이상 남아 있는 동안은 계속 리롤할 수 있다.

예를 들어 $R = 2$, $G = 2$이고 첫 판에서 리롤을 한 번 썼다면 첫 판이 끝난 뒤 RD는 $1.5$다. 다음 판에서 리롤을 쓰지 않으면 그 판이 끝난 뒤 RD는 $2.0$이다. 그다음 판에서도 리롤을 쓰지 않으면 RD는 여전히 $2.0$이다. $R = 2$를 넘을 수 없기 때문이다. 그다음 판에서 리롤을 두 번 쓰면 그 판이 끝난 뒤 RD는 $0.5$다.

챔피언 목록과 각 챔피언으로 게임했을 때 이길 확률이 주어진다. $10^{100}$판을 하면서 전략을 최적으로 고를 때의 기대 승률을 구하라. 판 수 $10^{100}$은 충분히 크므로, 답은 한 판당 기대 승률의 장기 평균을 최대화한 값과 소수점 아래 아홉째 자리까지 일치한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $N$, $R$, $G$가 공백으로 구분되어 주어진다. 다음 줄에는 실수 $P_1, P_2, \dots, P_N$이 공백으로 구분되어 주어진다. $P_i$는 $i$번째 챔피언으로 게임했을 때 이길 확률이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호이고, $y$는 $10^{100}$판을 했을 때의 기대 승률이다. $y$는 반올림해서 소수점 아래 아홉 자리를 정확히 채워 출력한다.

• $1 \le T \le 100$
• $1 \le N \le 1000$
• $1 \le R \le 20$
• $1 \le G \le 20$
• $0.0 \le P_i \le 1.0$
• $P_i$는 한 자리 숫자, 소수점, 네 자리 숫자 순서로 주어진다.

League of Legends는 Riot Games의 상표다. Riot Games는 이 문제를 보증하지 않고 이 문제와 아무 관련이 없다.