L. PepperLa's Express

Codeforces

IDCF10280L

Time2000ms

Memory128MB

Difficulty—

English · Original

Formal · Original

PepperLa's City is a three-dimensional city whose size is $(Z * X * Y)$. PepperLa Express is the only express in the city. The company has set up several delivery station in the city, and users will choose the nearest one. PepperLa's vehicle is poor, it can only travel along the $Z, X, Y$ axis at the speed of one unit length per day. Because many users complained about the delivery inefficiency, PepperLa decides to add a new delivery station in the open space. According to "barrel principle" PepperLa hopes to reduce the maximum delivery time. It means to minimize the maximum delivery time of all users. Could You help him find the best place? There are multiple test cases in this problem. For every test case, The first line has 3 interger, $Z, X, Y (1 <= Z, X, Y <= 10^2)$ Then following $Z times X$ lines each line contains $Y$ characters, the character in $i$'th row (start from 0), $j$'th column is $(z = floor.l i \/ X floor.r + 1, x = i % X + 1, y = j)$ '.' represents open space, '*' represents a user, '@' represents a delivery station. The input guarantees that there is at least one '.' and at least one '@'. $sum Z times X times Y <= 6 times 10^6$ For each test case, output a single line contains one integer,representing for the minimal delivery time. the best place to set up a new delivery station is $(z = 2, x = 2, y = 2)$ ## Input There are multiple test cases in this problem.For every test case, The first line has 3 interger, $Z, X, Y (1 <= Z, X, Y <= 10^2)$Then following $Z times X$ lines each line contains $Y$ characters, the character in $i$'th row (start from 0), $j$'th column is $(z = floor.l i \/ X floor.r + 1, x = i % X + 1, y = j)$'.' represents open space, '*' represents a user, '@' represents a delivery station.The input guarantees that there is at least one '.' and at least one '@'. $sum Z times X times Y <= 6 times 10^6$ ## Output For each test case, output a single line contains one integer,representing for the minimal delivery time. [samples] ## Note the best place to set up a new delivery station is $(z = 2, x = 2, y = 2)$

**Definitions** Let $ \mathbb{Z}^2 $ denote the 2D integer grid. Let $ f: \mathbb{Z}^2 \to \mathbb{N}_0 $ be the bijection assigning to each grid point $ (x, y) $ its unique number generated by BFS starting at $ (0,0) $, with exploration order: top $ (0,1) $, right $ (1,0) $, bottom $ (0,-1) $, left $ (-1,0) $. Let $ f^{-1}: \mathbb{N}_0 \to \mathbb{Z}^2 $ be the inverse function: $ f^{-1}(n) = (x, y) $ such that $ f(x, y) = n $. Let $ (x_{\text{curr}}, y_{\text{curr}}) \in \mathbb{Z}^2 $ denote the current position, initialized to $ (0, 0) $. **Input** Let $ T \in \mathbb{Z} $, $ 1 \le T \le 10^4 $, be the number of messages. Each message is one of two types: - Type 1: $ \texttt{1 id} $, where $ \texttt{id} \in \mathbb{N}_0 $ - Type 2: $ \texttt{2 x y} $, where $ x, y \in \mathbb{Z} $, $ |x| + |y| \le 10^8 $ **Objective** For each message: - If type 1: Compute $ (x, y) = f^{-1}(\texttt{id}) $, output $ (x - x_{\text{curr}}, y - y_{\text{curr}}) $, then set $ (x_{\text{curr}}, y_{\text{curr}}) \gets (x, y) $. - If type 2: Compute $ n = f(x, y) $, output $ n $, then set $ (x_{\text{curr}}, y_{\text{curr}}) \gets (x, y) $.

API Response (JSON)

{
  "problem": {
    "name": "L. PepperLa's Express",
    "description": {
      "content": "PepperLa's City is a three-dimensional city whose size is $(Z * X * Y)$. PepperLa Express is the only express in the city. The company has set up several delivery station in the city, and users will ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 131072
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10280L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "PepperLa's City is a three-dimensional city whose size is $(Z * X * Y)$.\n\nPepperLa Express is the only express in the city. The company has set up several delivery station in the city, and users will ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ \\mathbb{Z}^2 $ denote the 2D integer grid.  \nLet $ f: \\mathbb{Z}^2 \\to \\mathbb{N}_0 $ be the bijection assigning to each grid point $ (x, y) $ its unique number generated by BF...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments