시험 통과 확률 (대형 입력)

시간 제한5초메모리 제한512 MB

요약

제출 횟수 M과 문항별 독립 확률이 주어질 때, 한 번의 제출이 전부 정답일 확률이 최대가 되도록 답을 고른다.

난이도: 어려움10점 중 8점
유형: 확률, 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

데이브는 사지선다형 시험을 온라인으로 치른다. 답안은 여러 번 제출할 수 있지만, 모든 문항을 맞힌 제출이 하나라도 있어야 합격한다. 한 번 제출할 때 모든 문항에 답을 적어야 하고, 제출한 뒤에 알 수 있는 것은 합격 여부뿐이다.

데이브는 문항마다 네 보기가 각각 정답일 확률을 추정해 두었다. 이 확률은 다른 문항에 무엇을 적었는지와 독립이다. 제출 횟수가 정해져 있을 때, 데이브는 합격 확률이 가장 커지도록 답안을 고른다.

데이브가 최적으로 답안을 고를 때의 합격 확률을 구하라.

입력

첫 줄에 테스트 케이스의 개수 $C$ 가 주어진다. 이어서 $C$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 데이브가 제출할 수 있는 횟수 $M$ 과 시험의 문항 수 $Q$ 가 주어진다. 다음 $Q$ 개의 줄에는 각 문항의 보기 네 개가 정답일 확률이 차례로 주어진다. 확률은 모두 0 이상이고 소수점 아래 최대 여섯 자리까지 주어지며, 한 줄에 있는 네 확률의 합은 1이다.

제한

$1 \le C \le 100$
$1 \le Q \le 30$
$1 \le M \le 10000$

출력

각 테스트 케이스마다 한 줄에 Case #X: Y를 출력한다. $X$ 는 테스트 케이스 번호이고 1부터 시작한다. $Y$ 는 최대 합격 확률이며, 소수점 아래 여섯 자리로 반올림해 항상 여섯 자리를 채워 출력한다. 확률이 정확히 $0.5$ 라면 0.500000으로 출력한다.

예제2

예제 1

입력

3
10 2
0.25 0.25 0.25 0.25
0.25 0.25 0.25 0.25
64 3
0.3 0.4 0.0 0.3
1.0 0.0 0.0 0.0
0.2 0.2 0.2 0.4
3 2
0.5 0.17 0.17 0.16
0.5 0.25 0.25 0.0

예상 출력

Case #1: 0.625000
Case #2: 1.000000
Case #3: 0.500000

예제 2

입력

2
1 1
0.4 0.3 0.2 0.1
4 1
0.4 0.3 0.2 0.1

예상 출력

Case #1: 0.400000
Case #2: 1.000000