Задача 5. Межпланетный лифт Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 1 секунда

Ограничение по памяти: 512 мегабайт

Недавно у Мстителей появилась новая штаб-квартира. Первым делом Тони Старк решил уста-

новить там лифт, ведь не все умеют летать. Однако он не уследил за Халком, и тот в порыве гнева

поставил два лифта вместо одного. Позже он объяснил это тем, что два лифта могут перевозить в

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

Штаб-квартиру мстителей можно разбить на этажи. Дело происходило не на Земле, поэтому тут

очень много этажей (нет никаких ограничений в передвижении лифта), и даже есть отрицательные!

У каждого лифта есть своя программа строка длины M , состоящая из нулей и единиц. Если i-й

символ строки равен нулю, то эта команда опускает лифт вниз на один этаж, иначе поднимает

вверх (аналогично на один этаж). Если лифты столкнутся, то они сломаются. На данный момент

лифты не двигаются, а после запуска поедут одновременно и остановятся по истечении M секунд.

Железный человек отходил мир, поэтому не заметил этой проблемы. На данный момент

лифты находятся на этажах P1, P2 соответственно. До запуска лифтов Тони может успеть испра-

вить суммарно не более K команд. Другими словами, Железный человек может не более K раз

выбрать любую команду одного из лифтов и инвертировать ее если команда была равна единице,

Тони заменит ее на ноль, а если она была равна нулю, то он заменит ее на единицу. Тони может

инвертировать команды как первого, так и второго лифта несколько раз.

Необходимо написать программу, которая определяет, достаточно ли K исправлений команд,

чтобы лифты не столкнулись.

Форматвходныхданных

В первой строке вводятся числа M, K (1 6M 6105, 0 6K 62 ·105) длина программ и

количество секунд, оставшихся у Железного человека.

Во второй и третьей строках вводятся последовательности длины M , состоящие из нулей и

единиц, программы первого и второго лифтов.

В четвертой строке вводятся два числа P1, P2 (−109 6P1, P2 6109, P1 6= P2) позиции первого

и второй лифтов соответственно

Форматвыходныхданных

Если невозможно исправить не более K символов так, чтобы лифты не сломались, то в един-

ственной строке выведите ¾NO¿ (без кавычек).

Иначе в первой строке выведите ¾YES¿ (без кавычек), во второй исправленную первую про-

грамму, а в третьей исправленную вторую.

Если при текущих программах лифты не сломаются, то можно вывести программы без измене-

ний.

Системаоценки

за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи

и необходимых подзадач успешно пройдены.

подкайфом    3   07.12.2021 10:45    2