Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Посадка в самолет

(Время: 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.TXTOUTPUT.TXT
11 0
X.XX.X
X.XX.X
22 1
X.XX.X
..X...
X.XX.X
..XX..
33 2
X.XX.X
......
X..X.X
Impossible
41 103
.X.XXX
Impossible
56 7
X.....
......
....X.
X.....
......
..XX..
X....X
X....X
.X..X.
X....X
..XX..
..XX..

Замечание

Выше приведены пять примеров входных данных.

  1. В первом примере m = 0, а рассадка в самолете симметрична, поэтому итоговая рассадка совпадает с исходной.
  2. Во втором примере есть только один способ рассадить пассажиров симметрично.
  3. В третьем примере существовало бы решение, при m = 1, но при m = 2 не существует способа рассадить всех пассажиров симметрично.
  4. В четвертом примере требуется рассадить больше пассажиров чем свободных мест в самолете.
  5. Пятый примере соответствует ситуации, рассмотренной на рисунках в тексте условия. В этом примере существует несколько решений, приведено одно из них.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 A. Посадка в самолет
 B. Битоническая последовательность
 C. Игра с таблицей
 D. Выбор столицы
 E. Разбиение массива
 F. Бактерии
 G. Разбиение на тройки
 H. Обходы бинарного дерева

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru



естественные ссылки продвижение сайта