codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

929B.md (5080B)


      1 Source: https://codeforces.com/problemset/problem/929/B
      2 
      3 B. Места в самолёте
      4 
      5 ограничение по времени на тест
      6 
      7 1 секунда
      8 
      9 ограничение по памяти на тест
     10 
     11 256 мегабайт
     12 
     13 ввод
     14 
     15 стандартный ввод
     16 
     17 вывод
     18 
     19 стандартный вывод
     20 
     21 В самолёте есть *n* рядов мест. Если смотреть на ряды сверху, то в каждом ряду есть 3 места слева, затем проход между рядами, затем 4 центральных места, затем ещё один проход между рядами, а затем ещё 3 места справа.
     22 
     23 Известно, что некоторые места уже заняты пассажирами. Всего есть два вида пассажиров — статусные (те, которые часто летают) и обычные.
     24 
     25 Перед вами стоит задача рассадить ещё *k* обычных пассажиров так, чтобы суммарное число соседей у статусных пассажиров было минимально возможным. Два пассажира считаются соседями, если они сидят в одном ряду и между ними нет других мест и прохода между рядами. Если пассажир является соседним пассажиром для двух статусных пассажиров, то его следует учитывать в сумме соседей дважды.
     26 
     27 Входные данные
     28 
     29 В первой строке следуют два целых числа *n* и *k* (1 ≤ *n* ≤ 100, 1 ≤ *k* ≤ 10·*n*) — количество рядов мест в самолёте и количество пассажиров, которых нужно рассадить.
     30 
     31 Далее следует описание рядов мест самолёта по одному ряду в строке. Если очередной символ равен '-', то это проход между рядами. Если очередной символ равен '.', то это свободное место. Если очередной символ равен 'S', то на текущем месте будет сидеть статусный пассажир. Если очередной символ равен 'P', то на текущем месте будет сидеть обычный пассажир.
     32 
     33 Гарантируется, что количество свободных мест не меньше *k*. Гарантируется, что все ряды удовлетворяют описанному в условии формату.
     34 
     35 Выходные данные
     36 
     37 В первую строку выведите минимальное суммарное число соседей у статусных пассажиров.
     38 
     39 Далее выведите план рассадки пассажиров, который минимизирует суммарное количество соседей у статусных пассажиров, в том же формате, что и во входных данных. Если в свободное место нужно посадить одного из *k* пассажиров, выведите строчную букву 'x' вместо символа '.'.
     40 
     41 Примеры
     42 
     43 Входные данные
     44 
     45 ```
     46 1 2  
     47 SP.-SS.S-S.S
     48 ```
     49 
     50 Выходные данные
     51 
     52 ```
     53 5  
     54 SPx-SSxS-S.S
     55 ```
     56 
     57 Входные данные
     58 
     59 ```
     60 4 9  
     61 PP.-PPPS-S.S  
     62 PSP-PPSP-.S.  
     63 .S.-S..P-SS.  
     64 P.S-P.PP-PSP
     65 ```
     66 
     67 Выходные данные
     68 
     69 ```
     70 15  
     71 PPx-PPPS-S.S  
     72 PSP-PPSP-xSx  
     73 xSx-SxxP-SSx  
     74 P.S-PxPP-PSP
     75 ```
     76 
     77 Примечание
     78 
     79 В первом примере нужно посадить ещё двух обычных пассажиров. Для минимизации соседей у статусных пассажиров, нужно посадить первого из них на третье слева место, а второго на любое из оставшихся двух мест, так как независимо от выбора места он станет соседом двух статусных пассажиров.
     80 
     81 Изначально, у статусного пассажира, который сидит на самом левом месте уже есть сосед. Также на четвёртом и пятом местах слева сидят статусные пассажиры, являющиеся соседями друг для друга (что добавляет к сумме 2).
     82 
     83 Таким образом, после посадки ещё двух обычных пассажиров, итоговое суммарное количество соседей у статусных пассажиров станет равно пяти.