English · Original
Chinese · Translation
Formal · Original
You work at an airport, and you just received the baggage for a recently arrived flight, consisting of $k$ bags. You are in charge of placing these bags on the conveyor belt in the airport, which can be represented as a single, non self-intersecting ring.
Due to the COVID-19 pandemic, however, you want to place everyone's bags far apart on the conveyor belt.
Your task is to find the maximum distance $d$, such that it's possible to place all of the bags on the conveyor belt, and all of the bags that are next to each other on the conveyor belt will be at least $d$ units apart *at all times* during the conveyor belt's rotation. Assume that all parts of the conveyor belt move at the same speed.
Two bags are considered to be "next to each other" on the conveyor belt if you could travel from one bag to the other either clockwise or counter-clockwise on the conveyor belt, without encountering any other bags.
Note that in this problem, distance is measured in "Manhattan Distance", i.e. the Manhattan Distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is calculated as $lvert x_2 -x_1 rvert + lvert y_2 -y_1 rvert$.
The first line of input contains two space-separated positive integers $n$ $(1 < = n < = 200)$ and $k$ $(2 < = k < = 400)$: the length and width of the room that the baggage claim conveyor belt is in, and the number of bags on the upcoming flight, respectively.
The next $n$ lines contain $n$ characters each, representing the layout of the room. An "x" character represents part of the conveyor belt, while a "." character represents empty space.
The conveyor belt will be at most 400 characters long, i.e. there will be at most 400 "x" characters in the grid. The conveyor belt will also always be at least $k$ characters long.
The conveyor belt is guaranteed to be a single non-self-intersecting ring. Additionally, every conveyor belt space (every "x" character) will be directly adjacent (not diagonally) to exactly two other conveyor belt spaces.
Output a single positive integer $d$: the maximum distance, such that it's possible to place all of the bags on the conveyor belt at least $d$ units apart (in manhattan distance) at all times during the rotation of the conveyor belt.
Subtask 1 (15 points): there will be at most 15 $x$ characters in the input
Subtask 2 (61 points): no additional constraints
## Input
The first line of input contains two space-separated positive integers $n$ $(1 < = n < = 200)$ and $k$ $(2 < = k < = 400)$: the length and width of the room that the baggage claim conveyor belt is in, and the number of bags on the upcoming flight, respectively.The next $n$ lines contain $n$ characters each, representing the layout of the room. An "x" character represents part of the conveyor belt, while a "." character represents empty space.The conveyor belt will be at most 400 characters long, i.e. there will be at most 400 "x" characters in the grid. The conveyor belt will also always be at least $k$ characters long.The conveyor belt is guaranteed to be a single non-self-intersecting ring. Additionally, every conveyor belt space (every "x" character) will be directly adjacent (not diagonally) to exactly two other conveyor belt spaces.
## Output
Output a single positive integer $d$: the maximum distance, such that it's possible to place all of the bags on the conveyor belt at least $d$ units apart (in manhattan distance) at all times during the rotation of the conveyor belt.
[samples]
## Scoring
Subtask 1 (15 points): there will be at most 15 $x$ characters in the inputSubtask 2 (61 points): no additional constraints
[{"iden":"statement","content":"你为中央情报局工作，每天乘坐地铁上下班。地铁系统包含 $n$ 个车站，由 $m$ 条线路连接。你住在靠近车站 $a$ 的地方，工作地点靠近车站 $b$。每条线路包含一条指定的 $k_i$ 个车站的路线（列车要么按从第一个到最后一个的顺序行驶，要么按从最后一个到第一个的顺序行驶）。你可以保证，通过乘坐一条或多条地铁线路，可以在任意两个车站之间通行。\n\n不幸的是，你刚刚收到消息，一名敌方特工藏在地铁的某个车站中。你不确定特工具体藏在哪个车站，但你知道他一整天都会待在同一个车站。\n\n你仍然需要上下班，但你想避免与敌方特工出现在同一个车站。因此，你的任务是：对于每个车站，判断如果敌方特工藏在该车站，你是否仍能从家前往工作地点（并返回）。\n\n输入的第一行包含四个用空格分隔的整数 $n$、$m$、$a$ 和 $b$ $(1 \\le n, m \\le 10^5)$，$(1 \\le a, b \\le n)$，$(1 \\le \\sum k_i \\le 10^5)$：分别表示地铁系统中的车站数量、地铁线路数量、你居住附近的车站和工作附近的车站。\n\n此外，该地铁系统最多有 1000 个“枢纽站”（即多条线路经过的车站）。\n\n接下来的 $m$ 对行中，每对包含一个正整数 $k_i$，表示该线路服务的车站数量，以及一行包含 $k_i$ 个车站的序列，按顺序列出。\n\n请输出一个长度为 $n$ 的二进制字符串，其中字符 \"1\" 表示：如果敌方特工在该车站，你仍能往返工作；字符 \"0\" 表示不能。"}, {"iden":"input","content":"输入的第一行包含四个用空格分隔的整数 $n$、$m$、$a$ 和 $b$ $(1 \\le n, m \\le 10^5)$，$(1 \\le a, b \\le n)$，$(1 \\le \\sum k_i \\le 10^5)$：分别表示地铁系统中的车站数量、地铁线路数量、你居住附近的车站和工作附近的车站。此外，该地铁系统最多有 1000 个“枢纽站”（即多条线路经过的车站）。接下来的 $m$ 对行中，每对包含一个正整数 $k_i$，表示该线路服务的车站数量，以及一行包含 $k_i$ 个车站的序列，按顺序列出。"}, {"iden":"output","content":"输出一个长度为 $n$ 的二进制字符串，其中字符 \"1\" 表示：如果敌方特工在该车站，你仍能往返工作；字符 \"0\" 表示不能。"}, {"iden":"scoring","content":"完整题目：73 分"}, {"iden":"examples","content":"输入1\n5 3 1 10\n6\n1 2 3 4 5 6\n5\n2 7 8 9 10\n8\n11 2 12 13 9 14 15 6\n输出1\n001111110011111\n\n输入2\n8 3 3 5\n8\n1 2 3 18 4 5 6 7\n7\n10 9 8 2 11 12 13\n7\n15 14 9 4 13 16 17\n输出2\n110001111111111111"}, {"iden":"note","content":"以下是第一个示例的可视化表示： "}]
{"problem_iden":"CF9","statement_source":"Codeforces","problem_source":"CF","problem_statements":[{"iden":"statement","content":"你为中央情报局工作，每天乘坐地铁上下班。地铁系统包含 $n$ 个车站，由 $m$ 条线路连接。你住在靠近车站 $a$ 的地方，工作地点靠近车站 $b$。每条线路包含一条指定的 $k_i$ 个车站的路线（列车要么按从第一个到最后一个的顺序行驶，要么按从最后一个到第一个的顺序行驶）。你可以保证，通过乘坐一条或多条地铁线路，可以在任意两个车站之间通行。\n\n不幸的是，你刚刚收到消息，一名敌方特工藏在地铁的某个车站中。你不确定特工具体藏在哪个车站，但你知道他一整天都会待在同一个车站。\n\n你仍然需要上下班，但你想避免与敌方特工出现在同一个车站。因此，你的任务是：对于每个车站，判断如果敌方特工藏在该车站，你是否仍能从家前往工作地点（并返回）。\n\n输入的第一行包含四个用空格分隔的整数 $n$、$m$、$a$ 和 $b$ $(1 \\le n, m \\le 10^5)$，$(1 \\le a, b \\le n)$，$(1 \\le \\sum k_i \\le 10^5)$：分别表示地铁系统中的车站数量、地铁线路数量、你居住附近的车站和工作附近的车站。\n\n此外，该地铁系统最多有 1000 个“枢纽站”（即多条线路经过的车站）。\n\n接下来的 $m$ 对行中，每对包含一个正整数 $k_i$，表示该线路服务的车站数量，以及一行包含 $k_i$ 个车站的序列，按顺序列出。\n\n请输出一个长度为 $n$ 的二进制字符串，其中字符 \"1\" 表示：如果敌方特工在该车站，你仍能往返工作；字符 \"0\" 表示不能。"},{"iden":"input","content":"输入的第一行包含四个用空格分隔的整数 $n$、$m$、$a$ 和 $b$ $(1 \\le n, m \\le 10^5)$，$(1 \\le a, b \\le n)$，$(1 \\le \\sum k_i \\le 10^5)$：分别表示地铁系统中的车站数量、地铁线路数量、你居住附近的车站和工作附近的车站。此外，该地铁系统最多有 1000 个“枢纽站”（即多条线路经过的车站）。接下来的 $m$ 对行中，每对包含一个正整数 $k_i$，表示该线路服务的车站数量，以及一行包含 $k_i$ 个车站的序列，按顺序列出。"},{"iden":"output","content":"输出一个长度为 $n$ 的二进制字符串，其中字符 \"1\" 表示：如果敌方特工在该车站，你仍能往返工作；字符 \"0\" 表示不能。"},{"iden":"scoring","content":"完整题目：73 分"},{"iden":"examples","content":"输入1\n5 3 1 10\n6\n1 2 3 4 5 6\n5\n2 7 8 9 10\n8\n11 2 12 13 9 14 15 6\n输出1\n001111110011111\n\n输入2\n8 3 3 5\n8\n1 2 3 18 4 5 6 7\n7\n10 9 8 2 11 12 13\n7\n15 14 9 4 13 16 17\n输出2\n110001111111111111"},{"iden":"note","content":"以下是第一个示例的可视化表示： "}],"time_limit":1000,"memory_limit":262144}
**Definitions**
Let $ n, m, a, b \in \mathbb{Z}^+ $ denote the number of stations, number of subway lines, home station, and work station, respectively.
Let $ L = \{L_1, L_2, \dots, L_m\} $ be the set of subway lines, where each line $ L_i $ is an ordered sequence of $ k_i $ distinct stations: $ L_i = (s_{i,1}, s_{i,2}, \dots, s_{i,k_i}) $, representing a bidirectional route (train can travel both forward and backward).
Let $ G = (V, E) $ be the undirected graph of the subway system, where $ V = \{1, 2, \dots, n\} $ are stations, and $ E $ contains an edge between any two consecutive stations in any line $ L_i $.
Let $ H \subseteq V $ be the set of hub stations: $ H = \{ v \in V \mid \text{degree}(v) > 1 \} $, with $ |H| \leq 1000 $.
**Constraints**
1. $ 1 \leq n, m \leq 10^5 $
2. $ 1 \leq a, b \leq n $, $ a \neq b $
3. $ \sum_{i=1}^m k_i \leq 10^5 $
4. The graph $ G $ is connected.
5. At most 1000 hub stations exist.
**Objective**
For each station $ v \in \{1, 2, \dots, n\} $, determine whether there exists a path from $ a $ to $ b $ in $ G \setminus \{v\} $ (i.e., after removing station $ v $ and all incident edges).
Output a binary string $ S $ of length $ n $, where:
$$
S[v] =
\begin{cases}
1 & \text{if } a \text{ and } b \text{ are connected in } G \setminus \{v\} \\
0 & \text{otherwise}
\end{cases}
$$
API Response (JSON)
{
"problem": {
"name": "9. Plane and Simple",
"description": {
"content": "You work at an airport, and you just received the baggage for a recently arrived flight, consisting of $k$ bags. You are in charge of placing these bags on the conveyor belt in the airport, which can ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF9"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You work at an airport, and you just received the baggage for a recently arrived flight, consisting of $k$ bags. You are in charge of placing these bags on the conveyor belt in the airport, which can ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"你为中央情报局工作，每天乘坐地铁上下班。地铁系统包含 $n$ 个车站，由 $m$ 条线路连接。你住在靠近车站 $a$ 的地方，工作地点靠近车站 $b$。每条线路包含一条指定的 $k_i$ 个车站的路线（列车要么按从第一个到最后一个的顺序行驶，要么按从最后一个到第一个的顺序行驶）。你可以保证，通过乘坐一条或多条地铁线路，可以在任意两个车...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m, a, b \\in \\mathbb{Z}^+ $ denote the number of stations, number of subway lines, home station, and work station, respectively. \nLet $ L = \\{L_1, L_2, \\dots, L_m\\} $ be the...",
"is_translate": false,
"language": "Formal"
}
]
}