Места в самолёте
Contest: VK Cup 2018 - Квалификация 2
Difficulty rating: 1300
Tags: *special, implementation

В самолёте есть n рядов мест. Если смотреть на ряды сверху, то в каждом ряду есть 3 места слева, затем проход между рядами, затем 4 центральных места, затем ещё один проход между рядами, а затем ещё 3 места справа.

Известно, что некоторые места уже заняты пассажирами. Всего есть два вида пассажиров — статусные (те, которые часто летают) и обычные.

Перед вами стоит задача рассадить ещё k обычных пассажиров так, чтобы суммарное число соседей у статусных пассажиров было минимально возможным. Два пассажира считаются соседями, если они сидят в одном ряду и между ними нет других мест и прохода между рядами. Если пассажир является соседним пассажиром для двух статусных пассажиров, то его следует учитывать в сумме соседей дважды.

Input format:
В первой строке следуют два целых числа n и k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10·n) — количество рядов мест в самолёте и количество пассажиров, которых нужно рассадить.

Далее следует описание рядов мест самолёта по одному ряду в строке. Если очередной символ равен '-', то это проход между рядами. Если очередной символ равен '.', то это свободное место. Если очередной символ равен 'S', то на текущем месте будет сидеть статусный пассажир. Если очередной символ равен 'P', то на текущем месте будет сидеть обычный пассажир.

Гарантируется, что количество свободных мест не меньше k. Гарантируется, что все ряды удовлетворяют описанному в условии формату.

Output format:
В первую строку выведите минимальное суммарное число соседей у статусных пассажиров.

Далее выведите план рассадки пассажиров, который минимизирует суммарное количество соседей у статусных пассажиров, в том же формате, что и во входных данных. Если в свободное место нужно посадить одного из k пассажиров, выведите строчную букву 'x' вместо символа '.'.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
В первом примере нужно посадить ещё двух обычных пассажиров. Для минимизации соседей у статусных пассажиров, нужно посадить первого из них на третье слева место, а второго на любое из оставшихся двух мест, так как независимо от выбора места он станет соседом двух статусных пассажиров.

Изначально, у статусного пассажира, который сидит на самом левом месте уже есть сосед. Также на четвёртом и пятом местах слева сидят статусные пассажиры, являющиеся соседями друг для друга (что добавляет к сумме 2).

Таким образом, после посадки ещё двух обычных пассажиров, итоговое суммарное количество соседей у статусных пассажиров станет равно пяти.

Example input:
1 2
SP.-SS.S-S.S

Example output:
5
SPx-SSxS-S.S

Example input:
4 9
PP.-PPPS-S.S
PSP-PPSP-.S.
.S.-S..P-SS.
P.S-P.PP-PSP

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

Editorial:
Каждое из свободных мест характеризуется количеством статусных пассажиров, которые сидят на соседних местах с этим местом. Эта величина может быть равна нулю, одному или двум.
Так как нужно минимизировать суммарное количество соседей у статусных пассажиров, то выгоднее сначала сажать пассажиров в такие свободные места, у которых 0 статусных соседей, затем, если нужно, сажать пассажиров в такие свободные места, у которых 1 статусный сосед, а после этого, если нужно, сажать пассажиров в оставшиеся свободные места (у которых будет 2 статусных соседа).
Это можно сделать, например, с помощью вектора пар для свободных мест. В качестве первого элемента пары нужно хранить количество статусных соседей для текущего места, а вторым элементом должна быть пара — координаты текущего места. После этого нужно отсортировать вектор по неубыванию первого значения, и посадить k пассажиров в такие места, которым соответствуют первые k элементов отсортированного вектора.
После этого остаётся узнать суммарное количество соседей у статусных пассажиров. Это можно сделать с помощью одного прохода по всем местам в самолёте.