#2763 I.O.I

1 s   128 MB  

Description

 모두에게 비밀로 하고 있지만, 사실 재현이는 인기 아이돌 그룹의 멤버 ‘사과’로 활동하고 있다. 재현이는 그룹 내에서 귀여움을 담당하고 있는데, 이를 인정받아 국제적인 아이돌 축제인 I.O.I(International Olympiad of Idols)에 한국 대표로 선발되어 참가하게 되었다. 
 I.O.I 는 기본적으로 축제이지만, 이름에 걸맞게 국가대항전 형식의 대회가 진행된다. 참가하는 각 국가별로 아이돌 N 명을 뽑아 대표팀으로 선발하고, 토너먼트 방식으로 대결하여 최종 우승팀을 결정한다. 
 재현이의 귀여움을 앞세워 한국 팀은 무난하게 결승에 진출할 수 있었다. 결승전은 크게 단체전과 개인전으로 이루어 지는데, 그 중 개인전은 양 팀에서 한 경기에 각 팀에서 한 명씩 나와 각자 개인의 기량을 뽐내며 대결하는 방식으로, 총 N 번이 진행된다. 개인전에 무승부는 존재하지 않는다. 
 
각 팀의 대진표는 아래와 같은 방식으로 결정한다. 
1. 가위 바위 보를 진행하여 이긴 팀이 먼저 선택권을 가진다. 
2. 선택권을 가진 팀은 각 팀에서 아직 대진 상대가 정해지지 않은 한 명씩을 골라 그 둘을 대결 상대로 정한다. 그 이후 상대팀에게 선택권이 돌아간다. 
3. 2 의 과정을 반복하다가 모든 사람의 대진 상대가 결정되면, 그 뒤에 개인전을 시작한다. 
 
 대회가 진행되면서 결승에 진출한 두 팀은 상대에 대한 정보를 완벽히 파악했고, 각자 자기 팀의 선수들이 상대팀의 어떤 선수과 대결을 했을 때 승률이 어느 정도 될지 계산해두었다. 이 분석 결과는 객관적이기 때문에 두 팀의 분석 결과는 완전히 동일하다. 즉 A 팀이 A 팀의 p 선수와 B 팀의 q 선수가 대결할 경우 승률을 40%라고 분석했을 경우, B 팀은 B 팀의 q 선수와 A 팀의 p 선수가 대결할 경우 승률을 60%라고 분석한다는 것이다. 
 재현이는 두 팀 모두 최선의 전략으로 대결 상대를 정하려고 한다고 할 때, 한국 팀이 첫 가위바위보를 이겼을 때와 졌을 때 두 경우에 대하여 각각 개인전에서 한국이 승리하는 횟수의 기대값을 구하고자 한다. 

Input

 첫 줄에 각 팀에 소속된 선수의 수 N 이 주어진다. N 은 1 과 8 사이의 정수이다. 그 후 총 N 줄에 걸쳐 각 줄에 N 개의 숫자가 주어진다. i 번째 줄의 j 번째 숫자 pi,j는 한국 팀의 i 번째 선수와 j 번째 선수가 대결했을 한국팀이 승리할 확률을 나타낸다.

Output

 한국 팀이 가위바위보를 이겼을 때와 졌을 때의 승리하게 되는 대결의 수의 기대값을 공백으로 구분하여 출력한다. 출력한 답안과 실제 정답과의 오차가 10-6이하인 경우 답안으로 인정한다. 

Sample Input

Sample Output

2
0.1 0.7
0.5 0.3
1.20000 0.40000

Source

shake 2016! 본선