D. Checkerboard

Codeforces

IDCF10187D

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Byung is playing a game on her infinite checkerboard. The goal of the game is to move from a starting position (rs, cs) to a target position (rt, ct) using *exactly* x moves, where x is determined by a roll of a N-sided dice. A move consists in going from a square on the checkerboard to one of its four neighbors - up, down, left or right. Her dice is unbiased, meaning that every number from 1 to N has the same probability of being rolled. She's interested in knowing what's the number of different rolls that allow her to move to the target position in the last move. She can move to the same square more than once if she needs to. Can you help her? The input is composed by a single line containing 5 integers N (1 ≤ N ≤ 109), rs, cs, rt and ct ( - 109 ≤ rs, cs, rt, ct ≤ 109) indicating respectively the number of sides of the dice, the coordinates of the starting position and the coordinates of the target position. An integer number indicating the number of outcomes that she'll get a good roll. ## Input The input is composed by a single line containing 5 integers N (1 ≤ N ≤ 109), rs, cs, rt and ct ( - 109 ≤ rs, cs, rt, ct ≤ 109) indicating respectively the number of sides of the dice, the coordinates of the starting position and the coordinates of the target position. ## Output An integer number indicating the number of outcomes that she'll get a good roll. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of points. Let $ P = \{ (x_i, y_i, p_i) \mid i \in \{1, \dots, N\} \} $ be the set of points, where: - $ (x_i, y_i) \in \mathbb{R}^2 $ is the geographical position, - $ p_i \in \{ \text{PSD}, \text{PS} \} $ is the political preference. Let $ R_1, R_2 \subseteq \mathbb{R}^2 $ be axis-aligned rectangles such that $ R_1 \cap R_2 = \emptyset $. **Constraints** 1. $ R_1 $ and $ R_2 $ are axis-aligned rectangles (closed sets, including boundaries). 2. $ R_1 \cap R_2 = \emptyset $. **Objective** Maximize the total weighted count: $$ \max_{R_1, R_2} \left( \sum_{\substack{(x_i, y_i, p_i) \in P \\ (x_i, y_i) \in R_1 \\ p_i = \text{PSD}}} 1 + \sum_{\substack{(x_i, y_i, p_i) \in P \\ (x_i, y_i) \in R_2 \\ p_i = \text{PS}}} 1 \right) $$

API Response (JSON)

{
  "problem": {
    "name": "D. Checkerboard",
    "description": {
      "content": "Byung is playing a game on her infinite checkerboard. The goal of the game is to move from a starting position (rs, cs) to a target position (rt, ct) using *exactly* x moves, where x is determined by ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10187D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Byung is playing a game on her infinite checkerboard. The goal of the game is to move from a starting position (rs, cs) to a target position (rt, ct) using *exactly* x moves, where x is determined by ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of points.  \nLet $ P = \\{ (x_i, y_i, p_i) \\mid i \\in \\{1, \\dots, N\\} \\} $ be the set of points, where:  \n- $ (x_i, y_i) \\in \\mathbb{R}^2 $ is...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments