G. Game Scheduling

Codeforces
IDCF10193G
Time2000ms
Memory256MB
Difficulty
English · Original
Formal · Original
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) dot.op 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) dot.op 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 <= n <= 25$, $2 <= m <= 25$, $n dot.op m <= 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 "_-_". 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, \\dots texttt(B) n$ and so on. ## Input The input consists of a single line with two integers $n$ and $m$ ($1 <= n <= 25$, $2 <= m <= 25$, $n dot.op m <= 100$), the number of players in a team and the total number of teams, respectively. ## Output 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 "_-_". 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, \\dots texttt(B) n$ and so on. [samples]
**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 25 $, $ 2 \leq m \leq 25 $, $ nm \leq 100 $. Let $ T = \{T_1, T_2, \dots, T_m\} $ be the set of $ m $ teams, where each team $ T_i $ contains $ n $ players: $ T_i = \{P_{i,1}, P_{i,2}, \dots, P_{i,n}\} $. Let $ P = \bigcup_{i=1}^m T_i $ be the set of all players, with $ |P| = nm $. **Constraints** 1. Each player must play exactly $ (m-1)n $ games, each against a player from a different team. 2. In each round, a player may participate in at most one game. 3. Each player may have at most one bye (i.e., no game) across the entire schedule. 4. No intra-team games are allowed. 5. Each game is an unordered pair $ \{P_{i,a}, P_{j,b}\} $ with $ i \neq j $. **Objective** Construct a set of rounds $ R_1, R_2, \dots, R_r $, where $ r \leq (m-1)n + 1 $, such that: - Each round is a set of disjoint games (no player appears in more than one game per round). - Every valid inter-team pair $ (P_{i,a}, P_{j,b}) $ with $ i \neq j $ appears in exactly one round. - The number of players not playing in any round $ R_k $ is at most $ nm - 2 \cdot |R_k| $, and over all rounds, each player is benched at most once.
API Response (JSON)
{
  "problem": {
    "name": "G. Game Scheduling",
    "description": {
      "content": "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 play",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10193G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 play...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 25 $, $ 2 \\leq m \\leq 25 $, $ nm \\leq 100 $.  \nLet $ T = \\{T_1, T_2, \\dots, T_m\\} $ be the set of $ m $ teams, where each team $ T_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments