QOJ.ac

QOJ

Limite de temps : 2.0 s Limite de mémoire : 512 MB Points totaux : 100 Hackable ✓

#9347. 瑞士制比赛

Statistiques

瑞士轮(Swiss-system)是一种非淘汰制的比赛形式,其比赛轮数固定,但远少于循环赛。在瑞士轮比赛中,每位参赛者(团队或个人)不一定需要与所有其他参赛者进行比赛。当参赛人数过多,无法进行完整的循环赛,且不希望在比赛结束前淘汰任何参赛者时,通常会采用瑞士轮。瑞士轮常用于国际象棋、桥牌以及其他许多桌面游戏,如《万智牌》(Magic: the Gathering)和《游戏王》(Yu-Gi-Oh)。以下描述了某种瑞士轮比赛的规则。

比赛结构

比赛共进行 $m$ 轮,由 $n$ 名选手参加。为方便起见,选手拥有从 $1$ 到 $n$ 的唯一编号。在每一轮中,每位选手要么与另一位选手进行一场比赛,要么轮空(bye)。一场比赛由两到三局游戏组成,每局游戏可能平局或由其中一名选手获胜。当且仅当某位选手在前两局中均获胜时,才不进行第三局比赛。赢得局数较多的选手赢得该场比赛。如果两位选手赢得的局数相同,则该场比赛为平局。选手的排名由四个参数决定:比赛积分(Match Points, MP)、对手比赛胜率(Opponents’ match-win percentage, OMW)、游戏胜率(Game-win percentage, GW)和对手游戏胜率(Opponents’ game-win percentage, OGW)。你不需要知道如何确定选手的排名,因为本题不需要用到。

  • 比赛积分(Match Points):每赢得一场比赛,选手获得 3 分;每输掉一场比赛,获得 0 分;每场平局获得 1 分。
  • 游戏积分(Game Points):与比赛积分类似,每赢得一局游戏,选手获得 3 分;每局平局获得 1 分;每输掉一局游戏,获得 0 分。
  • 轮空(Byes):当选手在某一轮被分配轮空时,视为以 2-0-0 的成绩获胜(比赛结果记录格式为:胜-负-平)。因此,该选手获得 3 点比赛积分和 6 点游戏积分。
  • 比赛胜率(Match-win percentage):选手的比赛胜率是该选手累计的比赛积分除以这些轮次中可能获得的比赛积分总额(即轮数乘以 3)。如果该数值低于 $1/3$,则使用 $1/3$ 代替。这限制了低表现对计算和比较对手比赛胜率的影响。
  • 游戏胜率(Game-win percentage):与比赛胜率类似,选手的游戏胜率是该选手获得的游戏积分总额除以可能获得的游戏积分总额(即已进行的游戏局数乘以 3)。同样,如果实际游戏胜率低于 $1/3$,则使用 $1/3$ 代替。例如,如果一名选手在第 1 轮轮空(相当于 2-0-0 获胜),在第 2 轮以 2-0-1 获胜,在第 3 轮以 1-1-1 平局,那么他们的比赛胜率为 $(3 + 3 + 1)/(3 \times 3) = 7/9$,游戏胜率为 $(6 + 7 + 4)/(6 + 9 + 9) = 17/24$。
  • 对手比赛胜率(Opponents’ match-win percentage):一名选手的对手比赛胜率是该选手所面对的每位对手的比赛胜率的平均值(忽略选手轮空的轮次)。在计算每位对手的比赛胜率时,请使用上述定义,并始终使用每位对手当前的比赛胜率(在计算某一轮后的 OMW 时,使用每位对手在该轮之后的比赛胜率)。如果一名选手在比赛期间多次对阵同一位对手,则在计算平均值时,该对手的比赛胜率需计入相应次数。计算下述 OGW 时同样如此。
  • 对手游戏胜率(Opponents’ game-win percentage):与对手比赛胜率类似,一名选手的对手游戏胜率即为该选手所有对手的游戏胜率的平均值(同样忽略轮空)。如果一名选手没有参加任何比赛(所有轮次均轮空),则该选手的 OMW 和 OGW 均视为 $1/3$。

输入格式

输入包含多组数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$),表示数据组数。

对于每组数据,第一行包含两个整数 $n$ ($2 \le n \le 10\,000$) 和 $m$ ($1 \le m \le 16$),分别表示选手人数和比赛轮数。下一行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$,其中第 $i$ 个整数表示第 $i$ 轮的比赛场数 ($1 \le i \le m, 0 \le a_i \le n/2$)。

接下来的 $a_1 + a_2 + \dots + a_m$ 行,每行描述一场比赛。前 $a_1$ 行描述第一轮的比赛,接下来的 $a_2$ 行描述第二轮的比赛,依此类推。每场比赛由五个整数 $p_1, p_2, w_1, w_2, d$ ($1 \le p_1, p_2 \le n, p_1 \neq p_2, 0 \le w_1, w_2 \le 2, 0 \le d \le 3$) 描述,其中 $p_1$ 和 $p_2$ 表示两名选手的 ID,$w_1$ 和 $w_2$ 分别表示第一名选手和第二名选手赢得的局数。最后,$d$ 表示平局的游戏局数。保证 $w_1, w_2, d$ 代表比赛结构中定义的合法比赛结果,且每名选手在任何一轮中最多参加一场比赛。如果一名选手在某一轮中没有参加任何比赛,则视为该轮轮空。

保证所有数据组中 $n \cdot m$ 的总和不超过 $3 \cdot 10^5$。

输出格式

对于每组数据,输出应包含 $(n + 1) \cdot m$ 行,前 $n + 1$ 行描述第一轮后的结果,接下来的 $n + 1$ 行描述第二轮后的结果,依此类推。

对于每一轮,第一行打印字符串 “Round X”(不含引号),其中 X 为轮次编号。然后打印 $n$ 行,第 $i$ 行应包含四个空格分隔的数字,即第 $i$ 名选手在该轮后的 MP、OMW、GW 和 OGW。MP 应表示为整数,而 OMW、GW 和 OGW 应表示为形式为 $P/Q$ 的最简分数,其中 $P, Q$ 为正整数且 $P$ 与 $Q$ 的最大公约数为 1。详见样例输出。

样例

样例输入 1

2
2 3
0 1 1
1 2 2 0 1
1 2 1 1 1
3 2
1 1
1 2 0 2 0
2 3 2 0 0

样例输出 1

Round 1
3 1/3 1/1 1/3
3 1/3 1/1 1/3
Round 2
6 1/2 13/15 7/15
3 1/1 7/15 13/15
Round 3
7 4/9 17/24 11/24
4 7/9 11/24 17/24
Round 1
0 1/1 1/3 1/1
3 1/3 1/1 1/3
3 1/3 1/1 1/3
Round 2
3 1/1 1/2 1/1
6 1/2 1/1 1/2
3 1/1 1/2 1/1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.