ARAM

League of Legends™ 게임에서는 "모두 무작위, 모두 중앙"의 줄임말인 "ARAM"이라는 유형의 게임을 플레이할 수 있다. 이 문제는 비슷한 발상을 사용하지만, 문제를 이해하기 위해 League of Legends을 플레이해 본 적이 있을 필요는 없다.

ARAM 게임을 시작할 때마다 N명의 "champions" 중 하나가 균등한 확률로 무작위 배정된다. 어떤 챔피언으로는 다른 챔피언으로 플레이할 때보다 승리할 가능성이 더 높으므로, 운이 나쁘면 다른 챔피언을 배정받았으면 좋았겠다고 생각할 수 있다. 다행히도 게임에는 "Reroll" 기능이 있다.

리롤하면 아래에서 설명할 방식에 따라 챔피언이 무작위로 다시 배정되지만, 원할 때마다 리롤할 수 있는 것은 아니다. 리롤 능력은 일종의 화폐처럼 작동한다. 첫 ARAM 게임을 플레이하기 전에는 R RD("리롤 달러")를 가지고 시작한다. 적어도 1 RD를 가지고 있어야만 리롤할 수 있으며, 리롤하려면 1 RD를 사용해야 한다. 매 게임이 끝난 뒤 1/G RD(G는 정수)를 얻지만, R RD보다 많이 가질 수는 없다. R RD를 가진 상태에서 게임을 플레이하면, 그 게임이 끝난 뒤에도 여전히 R RD를 가지게 된다.

적어도 1RD를 가지고 있고 리롤하기로 선택하면, 1RD를 사용하고 N명의 챔피언 중 하나를 균등한 확률로 무작위 재배정받는다. 처음에 가지고 있던 챔피언과 같은 챔피언을 받을 가능성도 있다. 리롤로 받은 챔피언이 마음에 들지 않고 여전히 적어도 1RD가 남아 있다면 다시 리롤할 수 있다. 적어도 1RD가 남아 있는 동안에는 계속 리롤할 수 있다.

예를 들어, R=2이고 G=2이며 첫 게임에서 리롤을 한 번 사용한다면, 첫 게임이 끝난 뒤에는 1.5 RD를 가지게 된다. 게임을 하나 더 플레이하면서 이번에는 리롤을 사용하지 않으면 2.0 RD를 가지게 된다. 리롤을 사용하지 않고 게임을 하나 더 플레이하면 여전히 2.0 RD를 가지게 된다(R=2보다 많이 가질 수 없기 때문이다). 다음 게임에서 리롤을 두 번 사용하면, 그 게임이 끝난 뒤에는 0.5 RD를 가지게 된다.

챔피언 목록과 각 챔피언으로 게임을 플레이할 때 승리할 가능성이 주어진다. $10^{100}$번의 게임을 플레이하고 전략을 최적으로 선택한다면, 전체 게임 중 얼마의 비율로 승리할 것으로 예상되는가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 0.0 ≤ $P_{i}$ ≤ 1.0. $P_{i}$는 한 자리 숫자, 소수점, 그리고 4자리 숫자의 순서로 표현된다.

소규모 데이터 세트

시간 제한: 60초. 1 ≤ N ≤ 1000. 1 ≤ R ≤ 2. 1 ≤ G ≤ 3.

대규모 데이터 세트

시간 제한: 120초. 1 ≤ N ≤ 1000. 1 ≤ R ≤ 20. 1 ≤ G ≤ 20.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 세 정수 N, R, G가 포함된 줄로 시작한다. 다음 줄에는 공백으로 구분된 N개의 실수 $P_{i}$가 주어지며, 챔피언 i로 플레이할 경우 승리할 확률을 나타낸다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 $10^{100}$번의 게임을 플레이할 경우 승리하게 될 게임의 비율이다.

y가 정답과의 절대 오차 또는 상대 오차가 10^{-10} 이내이면 정답으로 간주된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참고한다.

League of Legends은 Riot Games의 상표이다. Riot Games은 Google Code Jam을 보증하지 않으며 이에 관여하지 않는다.