Лея: Я вложила информацию, жизненно важную для судьбы восстания, в память этого R2. Мой отец знает, как извлечь её оттуда. Вы должны доставить этого дроида в сохранности к нему на Альдераан.
В течение почти 25 лет император Палпатин управляет Империей, а Дарт Вейдер возглавляет имперские вооружённые силы.
Но сейчас Сопротивление как никогда сильно.
Одному из лидеров повстанцев, принцессе Лее с Альдераана, удалось завладеть секретными чертежами Звезды Смерти, имперской боевой станции.
Принцесса собиралась доставить план станции на тайную базу для дальнейшего изучения и поиска уязвимостей.
Но на её корабль нападает звёздный разрушитель «Devastator» во главе с Дартом Вейдером.
В последний момент принцесса Лея успевает отправить добытую информацию на близлежащую планету Татуин со своим дроидом R2-D2.
На этой планете, очень кстати, живёт старый друг её отца Оби-Ван Кеноби.
R2-D2 осознаёт всю важность возложенной на него принцессой миссии.
Он собирается зашифровать данные, чтобы они не смогли попасть не в те руки.
В памяти R2-D2 есть много файлов с изображениями.
Сначала он хотел воспользоваться известным алгоритмом скрытия информации.
Суть этого метода заключается в замене последних значащих битов изображения на биты скрываемого сообщения.
Изменение этих битов визуально не влияет на картинку, а потому никто и не подумает искать там информацию.
Но потом R2-D2 решил, что этот метод довольно известен и информация будет недостаточно защищена.
Тогда он решил изменить младшие биты изображения так, чтобы секретная информация составляла
непрерывную подпоследовательность байт файла изображения.
Помогите дроиду определить, возможно ли это.
И если да, то какое минимальное число битов ему придётся изменить.
Исходные данные
В первой строке входного файла даны целые числа n и m (1 ≤ n, m ≤ 250 000) —
размеры файлов с изображением и с секретной информацией в байтах.
Во второй строке задано содержимое файла с изображением, а в третьей — с секретной информацией.
Файлы заданы последовательностью байтов, разделённых пробелом.
Каждый байт записан как последовательность из восьми бит в порядке от старшего к младшему.
Результат
Выведите «No», если скрыть информацию в этом изображении невозможно.
В противном случае, в первой строке выведите «Yes»,
а во второй — количество бит, которые нужно поменять, и номер байта в файле с изображением,
начиная с которого будет записана секретная информация.
Если возможно несколько вариантов, выберите тот, в котором секретная информация записана
ближе к началу файла.
Примеры
исходные данные | результат |
---|
3 2
11110001 11110001 11110000
11110000 11110000
| Yes
1 2
|
3 1
11110000 11110001 11110000
11110000
| Yes
0 1
|
Автор задачи: Денис Дублённых (подготовка — Олег Долгоруков)