#P929B. Места в самолёте
-
ID: 4161
problem_type.undefined
ms
MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Места в самолёте
Cannot parse: NaNs error parsing time
Description
В самолёте есть n рядов мест. Если смотреть на ряды сверху, то в каждом ряду есть 3 места слева, затем проход между рядами, затем 4 центральных места, затем ещё один проход между рядами, а затем ещё 3 места справа.
Известно, что некоторые места уже заняты пассажирами. Всего есть два вида пассажиров — статусные (те, которые часто летают) и обычные.
Перед вами стоит задача рассадить ещё k обычных пассажиров так, чтобы суммарное число соседей у статусных пассажиров было минимально возможным. Два пассажира считаются соседями, если они сидят в одном ряду и между ними нет других мест и прохода между рядами. Если пассажир является соседним пассажиром для двух статусных пассажиров, то его следует учитывать в сумме соседей дважды.
В первой строке следуют два целых числа n и k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10·n) — количество рядов мест в самолёте и количество пассажиров, которых нужно рассадить.
Далее следует описание рядов мест самолёта по одному ряду в строке. Если очередной символ равен '-', то это проход между рядами. Если очередной символ равен '.', то это свободное место. Если очередной символ равен 'S', то на текущем месте будет сидеть статусный пассажир. Если очередной символ равен 'P', то на текущем месте будет сидеть обычный пассажир.
Гарантируется, что количество свободных мест не меньше k. Гарантируется, что все ряды удовлетворяют описанному в условии формату.
В первую строку выведите минимальное суммарное число соседей у статусных пассажиров.
Далее выведите план рассадки пассажиров, который минимизирует суммарное количество соседей у статусных пассажиров, в том же формате, что и во входных данных. Если в свободное место нужно посадить одного из k пассажиров, выведите строчную букву 'x' вместо символа '.'.
Input
В первой строке следуют два целых числа n и k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10·n) — количество рядов мест в самолёте и количество пассажиров, которых нужно рассадить.
Далее следует описание рядов мест самолёта по одному ряду в строке. Если очередной символ равен '-', то это проход между рядами. Если очередной символ равен '.', то это свободное место. Если очередной символ равен 'S', то на текущем месте будет сидеть статусный пассажир. Если очередной символ равен 'P', то на текущем месте будет сидеть обычный пассажир.
Гарантируется, что количество свободных мест не меньше k. Гарантируется, что все ряды удовлетворяют описанному в условии формату.
Output
В первую строку выведите минимальное суммарное число соседей у статусных пассажиров.
Далее выведите план рассадки пассажиров, который минимизирует суммарное количество соседей у статусных пассажиров, в том же формате, что и во входных данных. Если в свободное место нужно посадить одного из k пассажиров, выведите строчную букву 'x' вместо символа '.'.
Samples
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
Note
В первом примере нужно посадить ещё двух обычных пассажиров. Для минимизации соседей у статусных пассажиров, нужно посадить первого из них на третье слева место, а второго на любое из оставшихся двух мест, так как независимо от выбора места он станет соседом двух статусных пассажиров.
Изначально, у статусного пассажира, который сидит на самом левом месте уже есть сосед. Также на четвёртом и пятом местах слева сидят статусные пассажиры, являющиеся соседями друг для друга (что добавляет к сумме 2).
Таким образом, после посадки ещё двух обычных пассажиров, итоговое суммарное количество соседей у статусных пассажиров станет равно пяти.