문제
어느 날 학원에서 정쌤에게 문제 제작을 요청하였고, 모종의 루트를 통해 N개의 문제를 구하게 되었다.
하지만 불행하게도 정쌤이 구한 문제들의 데이터를 찾을 수 없었기 때문에 데이터를 만들어야 한다.
최근에 일이 많아 주어진 시간 내에 데이터 제작이 힘들다고 판단한 정쌤은 모의고사를 보지 않는 학생들에게 문제 데이터 제작을 맡기고자 한다.
문제 데이터 제작을 하게 되는 학생의 수는 문제 수와 동일한 N명이며, 각 학생은 무조건 한 개의 문제를 할당받게 된다.
각 학생들이 각 문제의 데이터 제작을 성공할 확률이 주어졌을 때, 확률이 최대가 되게 문제를 할당하는 프로그램을 작성하자.
입력
입력의 첫 번째 줄에는 정수 N이 주어진다(1≤N≤20). 그 다음 N개의 줄에는 0이상 100이하의 정수가 입력되며, 이는 퍼센테이지다. i번째줄의 j번째 숫자는 i번 학생이 문제를 번역할 수 있는 확률을 뜻한다.
출력
출력은 가능한 최대 번역 확률을 퍼센테이지로 출력한다. 주의: 출력은 정답 데이터와의 ±0.000001의 오차 이내에 들어가면 정답으로 간주한다.
예제 #1
2
100 100
50 50
50.50
예제 #2
2
0 50
50 0
25.00000
예제 #3
3
25 60 100
13 0 50
12 70 90
9.10000
출처
COCI 2006/2007 contest1 5
로그인해야 코드를 작성할 수 있어요.