아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

시험 합격 확률 (작은 입력)

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

요약
M번의 제출과 선택지 4개인 Q개 문항이 주어질 때, 각 제출의 통과 여부만 알 수 있는 상황에서 모든 문항을 맞힐 최대 확률을 구한다.
난이도

보통10점 중 7점

유형
동적 계획법, 확률, 조합론
정답자
아직 제출이 없습니다

문제

데이브는 인터넷으로 사지선다형 시험을 본다. 시험에는 문제가 QQ개 있고 문제마다 보기가 4개다. 한 번 제출할 때는 모든 문제에 답을 적어야 하고, 문제를 모두 맞혀야 합격한다. 제출한 뒤에 알 수 있는 것은 합격했는지 아닌지 하나뿐이다.

데이브는 문제마다 보기 4개가 각각 정답일 확률을 알고 있다. 이 확률은 문제끼리 서로 독립이다. 제출 횟수 MM이 정해져 있을 때, 데이브는 합격 확률이 가장 커지도록 답안을 고른다.

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

입력

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

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

  • 1≤C≤1001 \le C \le 100
  • 1≤Q≤61 \le Q \le 6
  • 1≤M≤10001 \le M \le 1000

출력

각 테스트 케이스마다 Case #X: Y 형식으로 한 줄씩 출력한다. XX는 1부터 시작하는 테스트 케이스 번호이고 YY는 합격 확률이다.

YY는 소수점 아래 일곱째 자리에서 반올림해 소수점 아래 6자리를 빠짐없이 채워 출력한다. 확률이 정확히 11이면 1.000000으로 출력한다. 이 문제의 데이터에서는 정답의 참값이 반올림 경계에서 10−910^{-9} 이상 떨어져 있다.

예제3

  1. 예제 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 1
0.25 0.25 0.25 0.25
    예상 출력
    Case #1: 0.250000

  3. 예제 3

    입력
    1
5 3
0.250000 0.250000 0.250000 0.250000
0.250000 0.250000 0.250000 0.250000
0.250000 0.250000 0.250000 0.250000
    예상 출력
    Case #1: 0.078125