L. Lazy ERCD

Codeforces

IDCF10185L

Time1000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

FIFA changed the style of the World Cup. There are no group rounds anymore, therefore the World Cup will be a pure knockout competition. In a knockout competition, each match that is played between two teams, the losing team is knocked-out of the competition and will not play again, until there's exactly one winner (we are not concerned about other positions, only the first place). Having N teams in the World Cup, our ERCD wants to know how many matches he needs to watch (he will really watch all matches). He is lazy to count that number, so he needs you to write a program that calculates it. The first line of the input contains a single integer 1 ≤ T ≤ 100 the number of test cases. Each test case consists of 1 line, containing a single integer N, the number of teams; where 1 ≤ N ≤ 100. For each test case output a single line displaying the case number, followed by the number of matches the ERCD will watch. ## Input The first line of the input contains a single integer 1 ≤ T ≤ 100 the number of test cases. Each test case consists of 1 line, containing a single integer N, the number of teams; where 1 ≤ N ≤ 100. ## Output For each test case output a single line displaying the case number, followed by the number of matches the ERCD will watch. [samples]

**Definitions** Let $ n \in \mathbb{Z}_{\geq 0} $, $ l \in \mathbb{Z}_{>0} $. Let $ I = \{ (x_i, y_i) \mid i \in \{1, \dots, n\} \} $ be the set of islands, where $ 0 < x_i < l $, $ -1000 \leq y_i \leq 1000 $, and all points are distinct. Let $ S = (0, 0) $ be the Reverse Mountain. Let $ T = (l, 0) $ be the New World entrance. **Graph Construction** Define a directed graph $ G = (V, E) $, where: - $ V = I \cup \{S, T\} $ - $ E = \{ (u, v) \mid u, v \in V, u \neq v, \, |x_u - x_v| + |y_u - y_v| \leq 5, \, x_u < x_v \} $ **Constraints** 1. $ 0 \leq n \leq 10^5 $ 2. $ 1 \leq l \leq 10^5 $ 3. For all $ (x_i, y_i) \in I $: $ 0 < x_i < l $, $ -1000 \leq y_i \leq 1000 $ 4. All island coordinates are distinct. 5. There exists at least one path from $ S $ to $ T $ in $ G $. **Objective** Find the maximum number of islands in $ I $ that can be visited on any path from $ S $ to $ T $ in $ G $. That is, compute: $$ \max_{P \in \mathcal{P}} \left( |P \cap I| \right) $$ where $ \mathcal{P} $ is the set of all directed paths from $ S $ to $ T $ in $ G $.

API Response (JSON)

{
  "problem": {
    "name": "L. Lazy ERCD",
    "description": {
      "content": "FIFA changed the style of the World Cup. There are no group rounds anymore, therefore the World Cup will be a pure knockout competition. In a knockout competition, each match that is played between tw",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10185L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "FIFA changed the style of the World Cup. There are no group rounds anymore, therefore the World Cup will be a pure knockout competition. In a knockout competition, each match that is played between tw...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}_{\\geq 0} $, $ l \\in \\mathbb{Z}_{>0} $.  \nLet $ I = \\{ (x_i, y_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of islands, where $ 0 < x_i < l $, $ -1000 \\leq y_i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments