English · Original
Chinese · Translation
Formal · Original
В самолёте есть _n_ рядов мест. Если смотреть на ряды сверху, то в каждом ряду есть 3 места слева, затем проход между рядами, затем 4 центральных места, затем ещё один проход между рядами, а затем ещё 3 места справа.
Известно, что некоторые места уже заняты пассажирами. Всего есть два вида пассажиров — статусные (те, которые часто летают) и обычные.
Перед вами стоит задача рассадить ещё _k_ **обычных** пассажиров так, чтобы суммарное число соседей у статусных пассажиров было минимально возможным. Два пассажира считаются соседями, если они сидят в одном ряду и между ними нет других мест и прохода между рядами. Если пассажир является соседним пассажиром для двух статусных пассажиров, то его следует учитывать в сумме соседей дважды.
## Входные Данные
В первой строке следуют два целых числа _n_ и _k_ (1 ≤ _n_ ≤ 100, 1 ≤ _k_ ≤ 10·_n_) — количество рядов мест в самолёте и количество пассажиров, которых нужно рассадить.
Далее следует описание рядов мест самолёта по одному ряду в строке. Если очередной символ равен '_\-_', то это проход между рядами. Если очередной символ равен '_._', то это свободное место. Если очередной символ равен '_S_', то на текущем месте будет сидеть статусный пассажир. Если очередной символ равен '_P_', то на текущем месте будет сидеть обычный пассажир.
Гарантируется, что количество свободных мест не меньше _k_. Гарантируется, что все ряды удовлетворяют описанному в условии формату.
## Выходные Данные
В первую строку выведите минимальное суммарное число соседей у статусных пассажиров.
Далее выведите план рассадки пассажиров, который минимизирует суммарное количество соседей у статусных пассажиров, в том же формате, что и во входных данных. Если в свободное место нужно посадить одного из _k_ пассажиров, выведите строчную букву '_x_' вместо символа '_._'.
## Примеры
Входные данные
1 2
SP.-SS.S-S.S
Выходные данные
5
SPx-SSxS-S.S
Входные данные
4 9
PP.-PPPS-S.S
PSP-PPSP-.S.
.S.-S..P-SS.
P.S-P.PP-PSP
Выходные данные
15
PPx-PPPS-S.S
PSP-PPSP-xSx
xSx-SxxP-SSx
P.S-PxPP-PSP
## Примечание
В первом примере нужно посадить ещё двух обычных пассажиров. Для минимизации соседей у статусных пассажиров, нужно посадить первого из них на третье слева место, а второго на любое из оставшихся двух мест, так как независимо от выбора места он станет соседом двух статусных пассажиров.
Изначально, у статусного пассажира, который сидит на самом левом месте уже есть сосед. Также на четвёртом и пятом местах слева сидят статусные пассажиры, являющиеся соседями друг для друга (что добавляет к сумме 2).
Таким образом, после посадки ещё двух обычных пассажиров, итоговое суммарное количество соседей у статусных пассажиров станет равно пяти.
[samples]
在飞机上有 #cf_span[n] 排座位。从上方看，每排有 #cf_span[3] 个左侧座位，接着是排间通道，然后是 #cf_span[4] 个中央座位，再一个排间通道，最后是 #cf_span[3] 个右侧座位。
已知某些座位已被乘客占据。总共有两种乘客：常旅客（经常飞行的）和普通乘客。
你的任务是安排另外 #cf_span[k] 个*普通*乘客，使得常旅客的总邻居数尽可能最小。两个乘客被视为邻居，当且仅当他们坐在同一排，且中间没有其他座位或排间通道。如果一个乘客是两个常旅客的邻居，则他应被计算两次。
第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 100], #cf_span[1 ≤ k ≤ 10·n]) —— 飞机上的排数和需要安排的乘客数。
接下来是飞机座位的描述，每行描述一排。如果当前字符为 '_-_'，则表示排间通道；如果为 '_._'，则表示空座位；如果为 '_S_'，则表示该座位上已有常旅客；如果为 '_P_'，则表示该座位上已有普通乘客。
保证空座位数量不少于 #cf_span[k]。保证所有排均符合题目描述的格式。
第一行输出常旅客的最小总邻居数。
接着输出最小化常旅客总邻居数的乘客安排方案，格式与输入相同。若需在某个空座位上安排一名 #cf_span[k] 名乘客之一，请用小写字母 '_x_' 替换 '_._'。
在第一个例子中，需要再安排两名普通乘客。为了最小化常旅客的邻居数，应将第一位乘客安排在左侧第三个座位，第二位乘客安排在剩余两个座位中的任意一个，因为无论选择哪个，他都会成为两个常旅客的邻居。
最初，坐在最左侧座位的常旅客已有一个邻居。此外，左侧第四和第五个座位上的常旅客互为邻居（这为总和增加了 #cf_span[2]）。
因此，在再安排两名普通乘客后，常旅客的总邻居数将变为五。
## Входные Данные
第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 100], #cf_span[1 ≤ k ≤ 10·n]) —— 飞机上的排数和需要安排的乘客数。接下来是飞机座位的描述，每行描述一排。如果当前字符为 '_-_'，则表示排间通道；如果为 '_._'，则表示空座位；如果为 '_S_'，则表示该座位上已有常旅客；如果为 '_P_'，则表示该座位上已有普通乘客。保证空座位数量不少于 #cf_span[k]。保证所有排均符合题目描述的格式。
## Выходные Данные
第一行输出常旅客的最小总邻居数。接着输出最小化常旅客总邻居数的乘客安排方案，格式与输入相同。若需在某个空座位上安排一名 #cf_span[k] 名乘客之一，请用小写字母 '_x_' 替换 '_._'。
## Примеры
输入
1 2
SP.-SS.S-S.S
输出
5
SPx-SSxS-S.S
输入
4 9
PP.-PPPS-S.SPSP-PPSP-.S..S.-S..P-SS.P.S-P.PP-PSP
输出
15
PPx-PPPS-S.SPSP-PPSP-xSxxSx-SxxP-SSxP.S-PxPP-PSP
## Примечание
在第一个例子中，需要再安排两名普通乘客。为了最小化常旅客的邻居数，应将第一位乘客安排在左侧第三个座位，第二位乘客安排在剩余两个座位中的任意一个，因为无论选择哪个，他都会成为两个常旅客的邻居。最初，坐在最左侧座位的常旅客已有一个邻居。此外，左侧第四和第五个座位上的常旅客互为邻居（这为总和增加了 #cf_span[2]）。因此，在再安排两名普通乘客后，常旅客的总邻居数将变为五。
[samples]
**Definitions:**
- Let $ n $ be the number of rows.
- Each row has a fixed seating configuration: 3 seats — aisle — 4 seats — aisle — 3 seats (total 10 seats per row).
- Seats are indexed left to right within a row as positions $ 0 $ to $ 9 $, where:
- Positions $ 0,1,2 $: left block,
- Positions $ 3,6 $: aisles (not seats),
- Positions $ 4,5,7,8 $: center block,
- Positions $ 9 $: rightmost seat.
- Let $ S $ be the set of seats currently occupied by **status** passengers.
- Let $ P $ be the set of seats currently occupied by **regular** passengers.
- Let $ F $ be the set of **free** seats (denoted by `_`).
- We must assign $ k $ new regular passengers to $ k $ distinct seats in $ F $, turning them into occupied seats (denoted by `x`).
**Adjacency Definition:**
Two occupied seats are **adjacent** if:
- They are in the same row,
- Their positions differ by exactly 1,
- Neither position is an aisle (i.e., positions 3 or 6 are not seats and break adjacency).
**Objective:**
Minimize the total number of **adjacent pairs** between any regular passenger and any status passenger, where:
- Each such pair contributes **1** to the sum.
- A single regular passenger adjacent to **two** status passengers contributes **2**.
Let $ T $ be the total sum over all status passengers of the number of adjacent regular passengers.
We seek to choose a subset $ X \subseteq F $, $ |X| = k $, to minimize $ T $.
**Constraints:**
- $ |F| \geq k $
- All rows follow the fixed 3-aisle-4-aisle-3 structure.
- Adjacency is only horizontal within a row; no vertical adjacency between rows.
**Output:**
- First line: minimal possible value of $ T $.
- Next $ n $ lines: the updated row configuration, with $ k $ free seats (`_`) replaced by `x` (assigned regular passengers), and all other seats unchanged.
**Formal Objective Function:**
Let $ A(s, r) = 1 $ if status seat $ s \in S $ and regular seat $ r \in P \cup X $ are adjacent, else 0.
Then:
$$
T = \sum_{s \in S} \sum_{r \in P \cup X} A(s, r)
$$
Minimize $ T $ over all choices of $ X \subseteq F $, $ |X| = k $.
**Note:** The adjacency graph is a union of $ n $ disjoint paths of length 10 (with positions 3 and 6 removed), each forming two disconnected segments: left block (positions 0–2) and center-right block (positions 4–5 and 7–9). Adjacency is only within these segments.
API Response (JSON)
{
"problem": {
"name": "B. Места в самолёте",
"description": {
"content": "В самолёте есть _n_ рядов мест. Если смотреть на ряды сверху, то в каждом ряду есть 3 места слева, затем проход между рядами, затем 4 центральных места, затем ещё один проход между рядами, а затем ещё",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF929B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "В самолёте есть _n_ рядов мест. Если смотреть на ряды сверху, то в каждом ряду есть 3 места слева, затем проход между рядами, затем 4 центральных места, затем ещё один проход между рядами, а затем ещё...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在飞机上有 #cf_span[n] 排座位。从上方看，每排有 #cf_span[3] 个左侧座位，接着是排间通道，然后是 #cf_span[4] 个中央座位，再一个排间通道，最后是 #cf_span[3] 个右侧座位。\n\n已知某些座位已被乘客占据。总共有两种乘客：常旅客（经常飞行的）和普通乘客。\n\n你的任务是安排另外 #cf_span[k] 个*普通*乘客，使得常旅客的总邻居数尽可能最小。两个乘客...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ n $ be the number of rows.\n- Each row has a fixed seating configuration: 3 seats — aisle — 4 seats — aisle — 3 seats (total 10 seats per row).\n- Seats are indexed left to rig...",
"is_translate": false,
"language": "Formal"
}
]
}