P13368 [GCJ 2011 #1B] RPI

在美国，每年有 350 所学校争夺 NCAA 大学篮球锦标赛的邀请资格。由于学校众多，如何决定哪些学校应该被邀请呢？大多数队伍之间从未交手，而且有些队伍的赛程比其他队伍要艰难得多。 下面是 $4$ 支队伍 $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$ 交手。 NCAA 锦标赛委员会使用一个叫做 RPI（Ratings Percentage Index，评级百分指数）的公式来帮助排名队伍。传统上，它被定义为： $$\text{RPI} = 0.25 \times \text{WP} + 0.50 \times \text{OWP} + 0.25 \times \text{OOWP}$$ WP、OWP 和 OOWP 对每支队伍的定义如下： - WP（胜率）是你赢得的比赛场次占总比赛场次的比例。 - 在示例赛程中，队伍 $A$ 的 WP = 1，队伍 $B$ 的 WP = 0，队伍 $C$ 的 WP = 2/3，队伍 $D$ 的 WP = 0.5。 - OWP（对手胜率）是你所有对手的 WP 的平均值，但首先要去掉他们与自己的比赛。 - 例如，如果去掉与 $D$ 队的比赛，$B$ 队的 WP = 0，$C$ 队的 WP = 0.5。因此，$D$ 队的 $\text{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$ 队的 $\text{OOWP} = 0.5 \times (0.5 + 2/3) = 7/12$。 综合计算，$A$ 队的 $\text{RPI} = (0.25 \times 1) + (0.5 \times 0.5) + (0.25 \times 7 / 12) = 0.6458333\dots $ 关于 RPI，你可以提出一些有趣的问题。RPI 是否合理地衡量了队伍的实力？对队伍来说，赢得比赛更重要，还是安排强劲的对手更重要？ 这些都是很好的问题，但对于本题，你的任务更为直接：给定一份比赛赛程，你能否计算出每支队伍的 RPI？

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为队伍数 $N$。 接下来的 $N$ 行，每行包含恰好 $N$ 个字符（'0'、'1' 或 '.'），表示赛程，格式与上面的示例相同。第 $i$ 行第 $j$ 列的 '1' 表示队伍 $i$ 战胜了队伍 $j$，'0' 表示队伍 $i$ 输给了队伍 $j$，'.' 表示队伍 $i$ 没有与队伍 $j$ 交手。

对于每组测试数据，输出 $N+1$ 行。第一行为 "Case #x:"，其中 $x$ 是测试编号（从 1 开始）。接下来的 $N$ 行，每行输出一支队伍的 RPI，顺序与输入赛程一致。 只要相对或绝对误差不超过 $10^{-6}$ 的答案都将被判为正确。

**数据范围** - $1 \leq T \leq 20$。 - 如果赛程中第 $i$ 行第 $j$ 列为 '1'，则第 $j$ 行第 $i$ 列为 '0'。 - 如果赛程中第 $i$ 行第 $j$ 列为 '0'，则第 $j$ 行第 $i$ 列为 '1'。 - 如果赛程中第 $i$ 行第 $j$ 列为 '.'，则第 $j$ 行第 $i$ 列也为 '.'。 - 每支队伍至少与另外两支队伍比赛过。 - 没有两支队伍之间会比赛两次。 - 没有队伍与自己比赛。 **小数据范围（8 分，测试点 1 - 可见）** - $3 \leq N \leq 10$。 - 时间限制：3 秒。 **大数据范围（12 分，测试点 2 - 隐藏）** - $3 \leq N \leq 100$。 - 时间限制：6 秒。 由 ChatGPT 4.1 翻译