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

NEERC 2013, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Шифровка 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
Автор задачи: Денис Дублённых (подготовка — Олег Долгоруков)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1996. Шифровка 3