RPI 계산 | cho.sh

문제

미국에서는 매년 350개 학교가 NCAA 대학 농구 토너먼트 초청장을 놓고 경쟁한다. 학교가 이렇게 많으면 누구를 초청할지 어떻게 정해야 할까? 대부분의 팀은 서로 한 번도 맞붙지 않고, 어떤 팀은 다른 팀보다 훨씬 어려운 일정을 치른다.

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는 0, C는 2/3, D는 0.5이다.
OWP(상대 승률)는 나와 치른 경기를 먼저 빼고 계산한 모든 상대의 WP를 평균한 값이다. D와 치른 경기를 빼면 B의 WP는 0, C의 WP는 0.5이므로 D의 OWP는 0.5 × (0 + 0.5) = 0.25이다. 같은 방법으로 A의 OWP는 0.5, B의 OWP는 0.5, C의 OWP는 2/3이다.
OOWP(상대의 상대 승률)는 모든 상대의 OWP를 평균한 값이다. 여기서 쓰는 OWP는 앞 단계에서 구한 값 그대로다. A의 OOWP는 0.5 × (0.5 + 2/3) = 7/12이다.

모두 합치면 A의 RPI는 (0.25 × 1) + (0.5 × 0.5) + (0.25 × 7/12) = 31/48이다.

RPI를 두고 던질 만한 질문은 여럿 있다. 팀의 실력을 재는 지표로 타당한가? 경기를 이기는 쪽과 강한 상대를 일정에 넣는 쪽 중 무엇이 더 중요한가? 이 문제에서 할 일은 더 단순하다. 일정이 주어질 때 모든 팀의 RPI를 구하라.

입력

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스의 첫 줄에는 팀의 수 $N$ 이 주어진다.

이어지는 $N$ 개 줄에는 각각 정확히 $N$ 개의 문자가 있다. 각 문자는 '0', '1', '.' 중 하나이고, 위 예시와 같은 형식으로 일정을 나타낸다. i행 j열이 '1'이면 팀 i가 팀 j를 이겼고, '0'이면 팀 i가 팀 j에게 졌으며, '.'이면 두 팀은 맞붙지 않았다.

제한

$1 \le T \le 20$
$3 \le N \le 10$
i행 j열이 '1'이면 j행 i열은 '0'이다.
i행 j열이 '0'이면 j행 i열은 '1'이다.
i행 j열이 '.'이면 j행 i열은 '.'이다.
모든 팀은 최소 두 팀과 경기한다.
같은 두 팀이 두 번 맞붙지 않는다.
어떤 팀도 자기 자신과 경기하지 않는다.

출력

각 테스트 케이스마다 $N + 1$ 개 줄을 출력한다. 첫 줄은 Case #x:이고, x는 1부터 시작하는 테스트 케이스 번호이다. 이어지는 $N$ 개 줄에는 일정에 나온 순서대로 각 팀의 RPI를 한 줄에 하나씩 출력한다.

RPI는 언제나 유리수이므로 기약분수 p/q 꼴로 출력한다. 분모 q는 양수여야 하고, p와 q의 최대공약수는 1이어야 한다. 값이 정수여도 분모를 생략하지 않는다. 값이 0이면 0/1로 출력한다.