RPI (Large) | cho.sh

문제

미국에서는 해마다 350개 학교가 대학 농구 토너먼트 초청장을 놓고 경쟁한다. 학교가 이렇게 많으니 누구를 부를지 정하기가 쉽지 않다. 서로 한 번도 맞붙지 않은 팀이 대부분이고, 일정이 유난히 험한 팀도 있다.

A, B, C, D 네 팀의 일정 예시는 다음과 같다.

 |ABCD
-+----
A|.11.
B|0.00
C|01.1
D|.10.

각 팀의 행에 있는 1은 승리, 0은 패배를 뜻한다. C는 B와 D를 이기고 A에게 졌다. A는 B와 C를 이겼고 D와는 경기한 적이 없다.

토너먼트 위원회는 팀 순위를 매길 때 RPI(Ratings Percentage Index)라는 공식을 쓴다.

$RPI = 0.25 \times WP + 0.50 \times OWP + 0.25 \times OOWP$

WP, OWP, OOWP는 팀마다 다음과 같이 정의한다.

WP(승률)는 자신이 치른 경기 중 이긴 비율이다. 예시 일정에서 A는 $WP = 1$ , B는 $WP = 0$ , C는 $WP = 2/3$ , D는 $WP = 0.5$ 이다.
OWP(상대 승률)는 상대 팀들의 WP를 평균한 값이다. 이때 상대가 자신과 치른 경기는 먼저 빼고 WP를 구한다. D와 치른 경기를 빼면 B는 $WP = 0$ , C는 $WP = 0.5$ 가 되므로 D는 $OWP = 0.5 \times (0 + 0.5) = 0.25$ 이다. 같은 방식으로 A는 $OWP = 0.5$ , B는 $OWP = 0.5$ , C는 $OWP = 2/3$ 이다.
OOWP(상대의 상대 승률)는 상대 팀들의 OWP를 평균한 값이며, 여기서 쓰는 OWP는 앞 단계에서 구한 값 그대로이다. A는 $OOWP = 0.5 \times (0.5 + 2/3) = 7/12$ 이다.

정리하면 A는 $RPI = (0.25 \times 1) + (0.5 \times 0.5) + (0.25 \times 7/12) = 0.6458333\ldots$ 이다.

RPI가 팀 실력을 제대로 재는 값인지, 경기를 이기는 쪽과 강한 상대를 일정에 넣는 쪽 중 무엇이 더 중요한지 같은 물음도 던질 수 있다. 이 문제에서 할 일은 더 단순하다. 경기 일정이 주어지면 모든 팀의 RPI를 계산하라.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 팀 수 $N$ 이 주어진다. 이어지는 $N$ 개 줄에는 위 예시와 같은 형식의 일정이 한 줄에 정확히 $N$ 글자씩 주어지고, 각 글자는 '0', '1', '.' 중 하나이다. i행 j열이 '1'이면 팀 i가 팀 j를 이겼고, '0'이면 팀 i가 팀 j에게 졌으며, '.'이면 두 팀은 맞붙은 적이 없다.

제한

$1 \le T \le 20$
i행 j열이 '1'이면 j행 i열은 '0'이다.
i행 j열이 '0'이면 j행 i열은 '1'이다.
i행 j열이 '.'이면 j행 i열도 '.'이다.
모든 팀은 적어도 두 팀과 경기한다.
같은 두 팀이 두 번 맞붙는 일은 없다.
자기 자신과 경기하는 팀은 없다.
$3 \le N \le 100$

출력

각 테스트 케이스마다 $N + 1$ 개 줄을 출력한다. 첫 줄은 "Case #x:"이고, x는 1부터 시작하는 테스트 케이스 번호이다. 이어지는 $N$ 개 줄에는 각 팀의 RPI를 일정에 주어진 순서대로 한 줄에 하나씩 출력한다. RPI는 소수점 아래 아홉째 자리까지 반올림해 정확히 아홉 자리로 출력한다.