{"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 центральных места, затем ещё один проход между рядами, а затем ещё 3 места справа.\n\nИзвестно, что некоторые места уже заняты пассажирами. Всего есть два вида пассажиров — статусные (те, которые часто летают) и обычные.\n\nПеред вами стоит задача рассадить ещё _k_ **обычных** пассажиров так, чтобы суммарное число соседей у статусных пассажиров было минимально возможным. Два пассажира считаются соседями, если они сидят в одном ряду и между ними нет других мест и прохода между рядами. Если пассажир является соседним пассажиром для двух статусных пассажиров, то его следует учитывать в сумме соседей дважды.\n\n## Входные Данные\n\nВ первой строке следуют два целых числа _n_ и _k_ (1 ≤ _n_ ≤ 100, 1 ≤ _k_ ≤ 10·_n_) — количество рядов мест в самолёте и количество пассажиров, которых нужно рассадить.\n\nДалее следует описание рядов мест самолёта по одному ряду в строке. Если очередной символ равен '_\\-_', то это проход между рядами. Если очередной символ равен '_._', то это свободное место. Если очередной символ равен '_S_', то на текущем месте будет сидеть статусный пассажир. Если очередной символ равен '_P_', то на текущем месте будет сидеть обычный пассажир.\n\nГарантируется, что количество свободных мест не меньше _k_. Гарантируется, что все ряды удовлетворяют описанному в условии формату.\n\n## Выходные Данные\n\nВ первую строку выведите минимальное суммарное число соседей у статусных пассажиров.\n\nДалее выведите план рассадки пассажиров, который минимизирует суммарное количество соседей у статусных пассажиров, в том же формате, что и во входных данных. Если в свободное место нужно посадить одного из _k_ пассажиров, выведите строчную букву '_x_' вместо символа '_._'.\n\n## Примеры\n\nВходные данные\n\n1 2\nSP.-SS.S-S.S\n\nВыходные данные\n\n5\nSPx-SSxS-S.S\n\nВходные данные\n\n4 9\nPP.-PPPS-S.S\nPSP-PPSP-.S.\n.S.-S..P-SS.\nP.S-P.PP-PSP\n\nВыходные данные\n\n15\nPPx-PPPS-S.S\nPSP-PPSP-xSx\nxSx-SxxP-SSx\nP.S-PxPP-PSP\n\n## Примечание\n\nВ первом примере нужно посадить ещё двух обычных пассажиров. Для минимизации соседей у статусных пассажиров, нужно посадить первого из них на третье слева место, а второго на любое из оставшихся двух мест, так как независимо от выбора места он станет соседом двух статусных пассажиров.\n\nИзначально, у статусного пассажира, который сидит на самом левом месте уже есть сосед. Также на четвёртом и пятом местах слева сидят статусные пассажиры, являющиеся соседями друг для друга (что добавляет к сумме 2).\n\nТаким образом, после посадки ещё двух обычных пассажиров, итоговое суммарное количество соседей у статусных пассажиров станет равно пяти.\n\n[samples]","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] 个*普通*乘客，使得常旅客的总邻居数尽可能最小。两个乘客被视为邻居，当且仅当他们坐在同一排，且中间没有其他座位或排间通道。如果一个乘客是两个常旅客的邻居，则他应被计算两次。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 100], #cf_span[1 ≤ k ≤ 10·n]) —— 飞机上的排数和需要安排的乘客数。\n\n接下来是飞机座位的描述，每行描述一排。如果当前字符为 '_-_'，则表示排间通道；如果为 '_._'，则表示空座位；如果为 '_S_'，则表示该座位上已有常旅客；如果为 '_P_'，则表示该座位上已有普通乘客。\n\n保证空座位数量不少于 #cf_span[k]。保证所有排均符合题目描述的格式。\n\n第一行输出常旅客的最小总邻居数。\n\n接着输出最小化常旅客总邻居数的乘客安排方案，格式与输入相同。若需在某个空座位上安排一名 #cf_span[k] 名乘客之一，请用小写字母 '_x_' 替换 '_._'。\n\n在第一个例子中，需要再安排两名普通乘客。为了最小化常旅客的邻居数，应将第一位乘客安排在左侧第三个座位，第二位乘客安排在剩余两个座位中的任意一个，因为无论选择哪个，他都会成为两个常旅客的邻居。\n\n最初，坐在最左侧座位的常旅客已有一个邻居。此外，左侧第四和第五个座位上的常旅客互为邻居（这为总和增加了 #cf_span[2]）。\n\n因此，在再安排两名普通乘客后，常旅客的总邻居数将变为五。\n\n## Входные Данные\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n ≤ 100], #cf_span[1 ≤ k ≤ 10·n]) —— 飞机上的排数和需要安排的乘客数。接下来是飞机座位的描述，每行描述一排。如果当前字符为 '_-_'，则表示排间通道；如果为 '_._'，则表示空座位；如果为 '_S_'，则表示该座位上已有常旅客；如果为 '_P_'，则表示该座位上已有普通乘客。保证空座位数量不少于 #cf_span[k]。保证所有排均符合题目描述的格式。\n\n## Выходные Данные\n\n第一行输出常旅客的最小总邻居数。接着输出最小化常旅客总邻居数的乘客安排方案，格式与输入相同。若需在某个空座位上安排一名 #cf_span[k] 名乘客之一，请用小写字母 '_x_' 替换 '_._'。 \n\n## Примеры\n\n输入\n1 2\nSP.-SS.S-S.S\n输出\n5\nSPx-SSxS-S.S\n\n输入\n4 9\nPP.-PPPS-S.SPSP-PPSP-.S..S.-S..P-SS.P.S-P.PP-PSP\n输出\n15\nPPx-PPPS-S.SPSP-PPSP-xSxxSx-SxxP-SSxP.S-PxPP-PSP\n\n## Примечание\n\n在第一个例子中，需要再安排两名普通乘客。为了最小化常旅客的邻居数，应将第一位乘客安排在左侧第三个座位，第二位乘客安排在剩余两个座位中的任意一个，因为无论选择哪个，他都会成为两个常旅客的邻居。最初，坐在最左侧座位的常旅客已有一个邻居。此外，左侧第四和第五个座位上的常旅客互为邻居（这为总和增加了 #cf_span[2]）。因此，在再安排两名普通乘客后，常旅客的总邻居数将变为五。\n\n[samples]","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 right within a row as positions $ 0 $ to $ 9 $, where:\n  - Positions $ 0,1,2 $: left block,\n  - Positions $ 3,6 $: aisles (not seats),\n  - Positions $ 4,5,7,8 $: center block,\n  - Positions $ 9 $: rightmost seat.\n- Let $ S $ be the set of seats currently occupied by **status** passengers.\n- Let $ P $ be the set of seats currently occupied by **regular** passengers.\n- Let $ F $ be the set of **free** seats (denoted by `_`).\n- We must assign $ k $ new regular passengers to $ k $ distinct seats in $ F $, turning them into occupied seats (denoted by `x`).\n\n**Adjacency Definition:**\n\nTwo occupied seats are **adjacent** if:\n- They are in the same row,\n- Their positions differ by exactly 1,\n- Neither position is an aisle (i.e., positions 3 or 6 are not seats and break adjacency).\n\n**Objective:**\n\nMinimize the total number of **adjacent pairs** between any regular passenger and any status passenger, where:\n- Each such pair contributes **1** to the sum.\n- A single regular passenger adjacent to **two** status passengers contributes **2**.\n\nLet $ T $ be the total sum over all status passengers of the number of adjacent regular passengers.\n\nWe seek to choose a subset $ X \\subseteq F $, $ |X| = k $, to minimize $ T $.\n\n**Constraints:**\n\n- $ |F| \\geq k $\n- All rows follow the fixed 3-aisle-4-aisle-3 structure.\n- Adjacency is only horizontal within a row; no vertical adjacency between rows.\n\n**Output:**\n\n- First line: minimal possible value of $ T $.\n- Next $ n $ lines: the updated row configuration, with $ k $ free seats (`_`) replaced by `x` (assigned regular passengers), and all other seats unchanged.\n\n**Formal Objective Function:**\n\nLet $ A(s, r) = 1 $ if status seat $ s \\in S $ and regular seat $ r \\in P \\cup X $ are adjacent, else 0.\n\nThen:\n$$\nT = \\sum_{s \\in S} \\sum_{r \\in P \\cup X} A(s, r)\n$$\n\nMinimize $ T $ over all choices of $ X \\subseteq F $, $ |X| = k $.\n\n**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF929B","tags":["implementation"],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}