← 返回题目列表

Codeforces · 929/B

B. 飞机座椅

中文机器翻译题面 查看原题

飞机上有 n 排座位。从上往下看,每排左边有3个座位,然后是两排之间的过道,然后是中间的4个座位,然后是两排之间的另一个过道,然后右边还有3个座位。

据了解,部分座位已被乘客占用。有两种类型的乘客 - 地位较高的乘客(经常飞行的乘客)和普通乘客。

你的任务是多安排 k 个普通乘客,使状态乘客的邻居总数尽可能最小。如果两名乘客坐在同一排,并且他们之间的排之间没有其他座位或通道,则他们被视为邻居。如果一名乘客是两个身份乘客的邻居乘客,那么他应该在邻居总和中被计算两次。

输入

第一行包含两个整数n和k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10·n)——飞机上的座位排数和需要就座的乘客人数。

以下是飞机座位排数的说明,每排一排。如果下一个字符是“-”,则这是行之间的通道。如果下一个字符是“.”,则这是一个可用空间。如果下一个符号等于“S”,则该状态乘客将坐在当前座位上。如果下一个符号是“P”,则普通乘客将坐在当前座位上。

保证空闲名额至少为k。确保所有行都满足条件中描述的格式。

输出

在第一行打印状态乘客的邻居的最小总数。

接下来,以与输入数据相同的格式输出使状态乘客的邻居总数最小化的乘客座位计划。如果您需要让 k 名乘客中的一名坐在空座位上,请打印小写字母“x”而不是符号“.”。

示例

输入 #1

1 2
SP.-SS.S-S.S

输出 #1

5
SPx-SSxS-S.S

输入 #2

4 9
PP.-PPPS-S.S
PSP-PPSP-.S.
.S.-S..P-SS.
P.S-P.PP-PSP

输出 #2

15
PPx-PPPS-S.S
PSP-PPSP-xSx
xSx-SxxP-SSx
P.S-PxPP-PSP

注意

在第一个示例中,您需要再登机两名普通乘客。为了尽量减少身份乘客的邻居,您需要将第一个座位安排在左起第三个座位上,将第二个座位安排在剩下的两个座位中的任何一个上,因为无论选择哪个座位,他都会成为两个身份乘客的邻居。

最初,坐在最左边座位的状态乘客已经有一个邻居。左边第四和第五位也是相邻的高地位乘客(总数增加了 2)。

因此,再有两名普通乘客登机后,状态乘客的邻居总数将为五个。