Задача 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¿ (без кавычек), во второй исправленную первую про-
грамму, а в третьей исправленную вторую.
Если при текущих программах лифты не сломаются, то можно вывести программы без измене-
ний.
Системаоценки
за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи
и необходимых подзадач успешно пройдены.
52 ∈ (2^5; 2^6)
Значит, вынимая 1 вариант из 52, мы получаем 6 бит информации.
2) Букв всего 6, и они все разные. Всего 6! = 720 вариантов.
2^9 = 512 < 720; 2^10 = 1024 > 720.
720 ∈ (2^9; 2^10)
Мы складываем 1 вариант из 720. Значит, мы получаем 10 бит.
3) 15% ~ 1/7. Опытный тренер может предположить, что всего есть 7 типов ошибок, и ошибка S - одна из них.
7 ∈ (4; 8) = (2^2; 2^3)
Поэтому он получит 3 бита информации.
Неопытный тренер не знает, сколько всего ошибок, и не может оценить частоту ошибки. Поэтому он получает 1 бит: допущена ошибка.
Хотя в последнем я не уверен.
Из нечетных вычли 1 (получилось четное число), к четным прибавили 1 (нечётное). Отменяем это: к четным прибавляем 1, от нечётных отнимаем.
3216 -> 2307
Третья цифра была сдвинута на 3, при этом поменяв свою четность. 2 - четное число, значит, исходное число было нечётным и было сдвинуто на 3 влево. Отменяем, сдвигаем на 3 вправо: 2 -> 3 -> 4 -> 5.
Вторая цифра была сдвинута на 2, чётность не меняла, была и осталась нечётной. Она была сдвинута на 2 разряда влево, нам надо сдвинуть на 2 вправо: 3 -> 4 -> 5.
Первая цифра сейчас чётная (0), значит, была нечётной, её сдвинули на 1 влево. Сдвигаем на 1 вправо: 0 -> 1.
Нулевая цифра была сдвинута на 0 разрядов, поэтому осталась без изменений. Это цифра 7.
Искомый пароль: 5517.
(Ну и на всякий случай: не надо ставить такие простые пароли, не будьте, как Вася!)