Problem G
Game Scheduling

Picture by Pat Paker via Wikimedia Commons, CC BY
In a tournament with $m$ teams, each team consisting of $n$ players, construct a playing schedule so that each player is paired up against all players in all teams except their own. That is, each player should play $(m-1) \cdot n$ games.

The playing schedule should be divided into rounds. A player can play at most one game per round. If a player does not play a game in a round, that player is said to have a bye in that round.

Your task is to write a program that constructs a playing schedule so that no player has a bye in more than $1$ round. In other words, the total number of rounds in the playing schedule should be no more than $(m-1) \cdot n + 1$.

The order of the rounds and games, and who is home and away in a game, does not matter.


The input consists of a single line with two integers $n$ and $m$ ($1 \le n \le 25$, $2 \le m \le 25$, $n \cdot m \le 100$), the number of players in a team and the total number of teams, respectively.


Output one line per round in the playing schedule. Each line should contain a space separated list of games. A game is in the format “<player>-<player>”. The players in the first team are denoted as $\texttt{A}1, \texttt{A}2, ..., \texttt{A}n$; the second team $\texttt{B}1, \texttt{B}2, \ldots \texttt{B}n$ and so on.

Sample Input 1 Sample Output 1
3 2
A1-B2 B1-A2 A3-B3
A2-B3 B2-A3 A1-B1
A3-B1 B3-A1 A2-B2
Sample Input 2 Sample Output 2
2 3
A1-B1 A2-C2 B2-C1
A1-C1 A2-B1 B2-C2
A1-B2 A2-C1 B1-C2
A1-C2 A2-B2 B1-C1
Sample Input 3 Sample Output 3
1 5
B1-E1 C1-D1
C1-A1 D1-E1
D1-B1 E1-A1
E1-C1 A1-B1
A1-D1 B1-C1

Please log in to submit a solution to this problem

Log in