H. Game of Corners

Codeforces

IDCF10079H

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Alice is playing the Game of Corners. She is given a rectangular grid with n rows and m columns. During one move, Alice can choose any two previously unused cell borders that have a common point and join them in a corner (pictured). A corner can be oriented in any way. Initially the grid is clear of corners. How many moves can Alice possibly make? The only line of the input contains two integers n and m (1 ≤ n, m ≤ 109) — the number of rows and the number of columns in the grid. Output a single integer — the maximum number of moves Alice can make. Two corners can share a point on the grid, but cannot share a cell border. For the first given sample, one possible arrangement of corners is: ## Input The only line of the input contains two integers n and m (1 ≤ n, m ≤ 109) — the number of rows and the number of columns in the grid. ## Output Output a single integer — the maximum number of moves Alice can make. [samples] ## Note Two corners can share a point on the grid, but cannot share a cell border.For the first given sample, one possible arrangement of corners is:

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the number of rows and columns of a rectangular grid, respectively. **Constraints** $ 1 \leq n, m \leq 10^9 $ **Objective** Compute the maximum number of non-overlapping corners that can be formed, where each corner is formed by joining two adjacent unused cell borders sharing a common grid point, and no two corners may share a cell border. Each corner occupies exactly one internal grid point and uses two of its four incident cell borders. The maximum number of such corners is constrained by the number of internal grid points and the bipartite nature of border usage. The grid has $ (n+1) \times (m+1) $ grid points. Each corner uses one grid point and consumes two of its four borders. Each cell border is shared between at most two adjacent cells, but each border segment can be used in at most one corner. The maximum number of corners is limited by the total number of available 90-degree turns at internal grid points, under the constraint that no two corners share a border. It is known that the maximum number of non-overlapping corners in such a grid is: $$ (n - 1)(m - 1) $$ **Answer** $$ (n - 1)(m - 1) $$

API Response (JSON)

{
  "problem": {
    "name": "H. Game of Corners",
    "description": {
      "content": "Alice is playing the Game of Corners. She is given a rectangular grid with n rows and m columns. During one move, Alice can choose any two previously unused cell borders that have a common point and j",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10079H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice is playing the Game of Corners. She is given a rectangular grid with n rows and m columns. During one move, Alice can choose any two previously unused cell borders that have a common point and j...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of rows and columns of a rectangular grid, respectively.\n\n**Constraints**  \n$ 1 \\leq n, m \\leq 10^9 $\n\n**Objective**  \nCompute the max...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments