레이팅 미적용설명
비밀 요원 더블오세븐, 그 유명한 본드(제임스 본드)를 모르는 사람은 없다. 덜 알려진 사실은 그가 실제로는 대부분의 임무를 직접 수행하지 않았다는 것이다. 임무는 대신 그의 사촌들, 지미 본드들이 수행했다. 본드(제임스 본드)는 새 임무를 받을 때마다 지미 본드들에게 임무를 배정하는 일에 지쳐서, 여러분에게 도움을 요청했다.
매달 본드(제임스 본드)는 임무 목록을 받는다. 과거 임무에서 얻은 상세한 정보를 이용하여, 그는 모든 임무와 모든 지미 본드에 대해 해당 지미 본드가 해당 임무를 성공적으로 완수할 확률을 계산한다. 여러분의 프로그램은 그 데이터를 처리하여, 모든 임무가 성공적으로 완수될 확률이 최대가 되는 배정을 찾아야 한다. 각 지미 본드는 정확히 하나의 임무를 배정받고, 각 임무는 정확히 한 명의 지미 본드에게 배정된다.
참고: 모든 임무가 성공적으로 완수될 확률은 각 임무가 성공적으로 완수될 확률의 곱과 같다.
제약
입력 형식
첫째 줄에 지미 본드의 수이자 임무의 수인 정수 \(N\) (\(1 \le N \le 20\))이 주어진다.
다음 \(N\)개의 줄에는 각각 \(0\) 이상 \(100\) 이하의 정수 \(N\)개가 주어진다. \(i\)번째 줄의 \(j\)번째 정수는 지미 본드 \(i\)가 임무 \(j\)를 성공적으로 완수할 확률(퍼센트)이다.
출력 형식
지미 본드들이 모든 임무를 성공적으로 완수할 최대 확률을 퍼센트로 출력한다.
참고: 공식 해와의 차이가 \(±0.000001\) 이내이면 정답으로 인정된다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 70점 |
예제 1
입력
2
100 100
50 50출력
50.000000예제 2
입력
2
0 50
50 0출력
25.00000예제 3
입력
3
25 60 100
13 0 50
12 70 90출력
9.10000문제 정보
태그