406386: GYM102394 C Competition in Swiss-system

A Swiss-system tournament is a non-eliminating tournament format that features a set number of rounds of competition, but considerably fewer than that of a round-robin tournament. In a Swiss tournament, each competitor (team or individual) does not necessarily play all other entrants. A Swiss system is used for competitions in which the number of entrants is considered too large for a full round-robin to be feasible, and eliminating any competitors before the end of the tournament is undesirable. Swiss systems are commonly used in chess, bridge and many other tabletop games such as Magic: the Gathering and Yu-Gi-Oh. The following describes the rules of a certain tournament with Swiss-system.

Tournament structure: The tournament consists of $$$m$$$ rounds and is contested by $$$n$$$ players. The players are given unique IDs from $$$1$$$ to $$$n$$$ for convenience. In each round, each player either plays a match against another player or receives a bye. A match consists of two or three games, where each game may be a draw or won by one of the players. The third game is not played if and only if either player manages to win both the first and the second game. The player who wins the higher number of games wins the match. If both players win the same number of games, then the match is a draw. A player's rank is determined by four parameters: Match Points (MP), Opponents' match-win percentage (OMW), Game-win percentage (GW) and Opponents' game-win percentage (OGW). You don't need to know how to determine a player's rank since it is not needed for this problem.

Match Points: Players earn 3 match points for each match win, 0 points for each match loss and 1 match point for each match ending in a draw.

Game Points: Game points are similar to match points in that players earn 3 game points for each game they win and 1 point for each game that ends in a draw, and 0 points for any game lost.

Byes: When a player is assigned a bye for a round, they are considered to have won the match 2-0-0 (match results are recorded in this format: Wins–Losses–Draws). Thus, that player earns 3 match points and 6 game points.

Match-win percentage: A player's Match-win percentage is that player's accumulated match points divided by the total match points possible in those rounds (which is 3 times the number of rounds). If this number is lower than $$$1/3$$$, use $$$1/3$$$ instead. This limits the effect low performances have when calculating and comparing Opponents' match-win percentage.

Game-win percentage: Similar to the Match-win percentage, a player's Game-win percentage is the total number of game points they earned divided by the total game points possible (3 times the number of games played). Again, use $$$1/3$$$ if the actual game-win percentage is lower than that. For example, if a player receives a bye in round 1 (which is equivalent to winning 2-0-0), and wins 2-0-1 in round 2, then draws 1-1-1 in round 3, then their Match-win percentage is $$$(3+3+1)/(3\times 3)=7/9$$$, and their Game-win percentage is $$$(6+7+4)/(6+9+9)=17/24$$$.

Opponents' match-win percentage: A player's Opponents' match-win percentage is the average Match-win percentage of each opponent that player faced (ignoring those rounds for which the player received a bye). Use the definition listed above when calculating each opponent's Match-win percentage, and always use each opponents' current Match-win percentage (when calculating the OMW after a round, use each opponents' Match-win percentage after that round). If a player plays against the same opponent multiple times during the tournament, then that opponent's Match-win percentage is used that many times when calculating the average. The same is true when calculating the OGW, which is defined below.

Opponents' game-win percentage: Similar to Opponents' match-win percentage, a player's Opponents' game-win percentage is simply the average game-win percentage of all of that player's opponents (again, byes are ignored). If a player has not played any matches (they receive byes for all the rounds), then both the OMW and the OGW of that player are considered to be $$$1/3$$$.

Because you are a famous programmer, the tournament organiser asked you to write a program to help him run the tournament. You are given the results of each match of each round of this tournament, and you need to calculate the MP, OMW, GW and OGW of each player after each round so that the tournament organiser will be able to determine the rankings of the players much more quickly.

The input contains multiple cases. The first line of the input contains a single integer $$$T\ (1 \le T \le 10^5)$$$, the number of cases.

For each case, the first line of the input contains two integers $$$n\ (2 \le n \le 10\,000)$$$ and $$$m\ (1 \le m \le 16)$$$, the number of players and the number of rounds respectively. The following line contains $$$m$$$ integers $$$a_1,a_2,\dots,a_m$$$ where the $$$i$$$-th integer denotes the number of matches in the $$$i$$$-th round ($$$1 \le i \le m,\ 0 \le a_i \le \left \lfloor{n/2}\right \rfloor$$$).

The following $$$a_1+a_2+\dots+a_m$$$ lines each describes a match. The first $$$a_1$$$ lines describe matches in the first round, the next $$$a_2$$$ lines describe matches in the second round, and so on. Each match is described by five integers $$$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)$$$, where $$$p_1$$$ and $$$p_2$$$ denote the IDs of the two players in the match, and $$$w_1$$$ and $$$w_2$$$ denote the number of games won by the first player and the second player, respectively. Finally, $$$d$$$ denotes the number of games that ended in a draw. It is guaranteed that $$$w_1,w_2,d$$$ represents a legal match result defined in the tournament structure and that each player appears in no more than one match in any single round. If a player doesn't appear in any matches for a round, then that player is considered to have been assigned a bye for that round.

It is also guaranteed that the sum of $$$n\cdot m$$$ over all cases doesn't exceed $$$3\cdot 10^5$$$.

The output for each case should contain $$$(n+1)\cdot m$$$ lines, where the first $$$n+1$$$ lines describe the results after the first round, the next $$$n+1$$$ lines describe the results after the second round, and so on.

For each round, print the string "Round X" (without quotes) in the first line, where X is the number of the round. Then print $$$n$$$ lines, where the $$$i$$$-th line should contain four space-separated numbers, the MP, OMW, GW and OGW of the $$$i$$$-th player after this round. The MP should be represented by an integer, while the OMW, GW and OGW should be represented by a simple irreducible fraction in the form of $$$P/Q$$$, where $$$P,Q$$$ are positive integers and the greatest common divisor of $$$P$$$ and $$$Q$$$ is 1. See the sample output for details.

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

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