레드 테이프 위원회

당신은 Department of Redundancy Reduction 및 Superfluity Shrinkage의 책임자이다. 현재 이 부서는 부서 자체에 "레드 테이프"(비효율성)가 너무 많은지를 두고 합의하지 못하고 있다. 부서에서는 이 문제에 대해 투표할 Red Tape Committee을 구성해 달라고 요청했다.

부서에는 N명의 구성원이 있다. 각 구성원에 대해, 그 구성원이 "Yes"에 투표할 확률 $P_{i}$를 알고 있다. 구성원이 "Yes"에 투표하지 않으면 반드시 "No"에 투표하며, 기권하는 사람은 없다.

위원회에 참여할 구성원을 정확히 K명 선택해야 한다. 부서 규칙에 따르면 동률이 가능하도록 K는 짝수여야 하며, 동률은 건전한 관료제의 일부로 여겨진다.

동률이 될 확률을 최대화하도록 위원회 구성원을 선택한다면, 그 확률은 얼마인가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 2 ≤ K ≤ N. K는 짝수이다. 0.00 ≤ 각각의 $P_{i}$ ≤ 1.00.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 60초. 2 ≤ N ≤ 16.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 120초. 2 ≤ N ≤ 200.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 테스트 케이스의 첫 줄에는 부서와 위원회의 크기를 나타내는 두 정수 N과 K가 주어진다. 테스트 케이스의 둘째 줄에는 N개의 십진수 값 $P_{i}$가 주어진다. 각 값은 정확히 소수점 이하 두 자리의 정밀도를 가지며 i번째 부서 구성원이 "Yes"에 투표할 확률을 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y은 가능한 최대 동률 확률을 나타내는 부동소수점 수이다. y은 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 대한 설명은 FAQ을 참고하라.

예제 케이스 #1에서는 이용 가능한 부서 구성원이 두 명뿐이므로 두 명 모두를 위원회에 포함해야 한다. 이 위원회에서는 두 위원이 서로 다르게 투표할 때에만 동률이 되며, 이는 전체 경우의 절반에 해당한다. (일반성을 잃지 않고 첫 번째 사람의 표를 정하자. 그러면 두 번째 사람이 반대쪽에 투표할 확률은 0.5이다.)

예제 케이스 #2에서 최선의 전략은 0.00일 확률이 "Yes"인 구성원 중 한 명과 1.00일 확률이 "Yes"인 구성원 중 한 명을 선택하는 것이다. 이렇게 하면 동률이 보장된다.

예제 케이스 #3에서 0.50와 0.75의 "Yes" 확률을 가진 두 구성원을 선택한다고 하자. 첫 번째 사람이 "Yes"에 투표하고 두 번째 사람이 "No"에 투표하거나(확률 0.5 * 0.25 = 0.125), 첫 번째 사람이 "No"에 투표하고 두 번째 사람이 "Yes"에 투표하면(확률 0.5 * 0.75 = 0.375) 동률이 된다. 따라서 동률이 될 총확률은 0.125 + 0.375 = 0.5이다. 0.50와 1.00의 "Yes" 확률을 가진 두 구성원을 선택해도 동률 확률은 0.5가 된다. 1.00 구성원이 "Yes"에 투표하고 0.50 구성원은 반드시 "No"에 투표해야 하기 때문이다. 0.75와 1.00의 "Yes" 확률을 가진 두 구성원을 선택하면 동률 확률은 0.25에 불과하다. 1.00 구성원이 "Yes"에 투표하고 0.75 구성원은 반드시 "No"에 투표해야 하기 때문이다. 따라서 우리가 얻을 수 있는 최선은 0.5이다.