|
Посадка в самолет
(Время: 1 сек. Память: 32 Мб Сложность: 24%)
В самолетах авиакомпании Битавиа кресла расположены в n рядов, при этом в каждом ряду по шесть мест, между третьим и четвертым местом находится проход. Некоторые пассажиры регистрируются заранее онлайн, другие пассажиры регистрируются на стойке регистрации в аэропорту.
При онлайн-регистрации пассажир может выбрать любое место и не может его затем менять. Например, при n = 6 рассадка в самолете после онлайн-регистрации может выглядеть так (крестиками
отмечены занятые места):
На стойку регистрации придут m пассажиров. По правилам Битавиа нужно рассадить их в самолете таким образом, чтобы итоговая рассадка в самолете была симметрична относительно прохода.
То есть, если в некотором ряду на первом кресле сидит пассажир, то в том же ряду на шестом кресле
тоже должен сидеть пассажир. То же самое справедливо для второго и пятого, третьего и четвертого кресел, соответственно. При этом пересаживать пассажиров, прошедших онлайн-регистрацию
нельзя. В исходную рассадку, показанную на рисунке выше, можно добавить семь пассажиров, удовлетворив условие симметрии, например, следующим образом:
Вам дана рассадка пассажиров после онлайн-регистрации. Требуется рассадить m пассажиров
так, чтобы итоговая рассадка в самолете была симметрична относительно прохода, или определить,
что это невозможно.
Входные данные
В первой строке входного файла INPUT.TXT содержатся два целых числа n и m — количество рядов в самолете и количество
пассажиров, которые придут на стойку регистрации (1 ≤ n ≤ 1000, 0 ≤ m ≤ 6000).
В следующих n строках задана изначальная рассадка в самолете после онлайн-регистрации. В
каждой строке содержится по шесть символов, при этом i-й символ j-й строки равен «X» (заглавная
английская X), если i-е место в j-м ряду уже занято и «.» (точка) иначе.
Выходные данные
В выходной файл OUTPUT.TXT выведите «Impossible», если искомой рассадки не существует.
Иначе выведите n строк по шесть символов — итоговую рассадку в самолете. При этом i-й
символ j-й строки должен быть равен «X», если место занято, и «.», если свободно. Если существует
несколько решений, разрешается вывести любое.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 1 0 X.XX.X | X.XX.X |
2 | 2 1 X.XX.X ..X... | X.XX.X ..XX.. |
3 | 3 2 X.XX.X ...... X..X.X | Impossible |
4 | 1 103 .X.XXX | Impossible |
5 | 6 7 X..... ......
....X.
X.....
......
..XX.. | X....X
X....X
.X..X.
X....X
..XX.. ..XX.. |
Замечание
Выше приведены пять примеров входных данных.
- В первом примере m = 0, а рассадка в самолете симметрична, поэтому итоговая рассадка
совпадает с исходной.
- Во втором примере есть только один способ рассадить пассажиров симметрично.
- В третьем примере существовало бы решение, при m = 1, но при m = 2 не существует способа
рассадить всех пассажиров симметрично.
- В четвертом примере требуется рассадить больше пассажиров чем свободных мест в самолете.
- Пятый примере соответствует ситуации, рассмотренной на рисунках в тексте условия. В этом
примере существует несколько решений, приведено одно из них.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |