ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1996. Шифровка 3

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Лея: Я вложила информацию, жизненно важную для судьбы восстания, в память этого 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
Автор задачи: Денис Дублённых (подготовка — Олег Долгоруков)