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

Ural SU Team.GOV contest. Petrozavodsk training camp. Summer 2011

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

A. GOV-стажировка

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Здравствуйте, Денис!

Ваша GOV-стажировка закончена. К сожалению, мы не сможем принять Вас на постоянную основу. Не расстраивайтесь — Вы не первый и не последний. С Вами было приятно работать. Успехов!

С уважением, капитан Ural SU Team.GOV, Вадим Канторов.

Холодный ноябрьский вечер 2010 года. Общежитие матмеха УрГУ. Тусклый свет монитора. Так покинул команду Team.GOV её восьмой по счёту игрок — Ден Мухаметьянов.
В начале осени Ден вернулся с жарких каникул и спокойно просматривал фото из путешествия, когда получил письмо «Вы приглашены на собеседование в Team.GOV». Год назад об этом можно было лишь мечтать…
Картинка всплывает перед глазами, словно это было вчера. Маленькая уютная комната, Вадик удобно расположился в кресле-качалке. Ден неловко кашлянул и потоптался на месте. Вадик поднял глаза и улыбнулся.
— Какой у вас стаж?
— Полгода в Ural SU AirBug и полгода в Ural SU Quickov.
— Хм, неплохо. Любимая тема?
— Строковые алгоритмы люблю…
— Ну тогда сразу к делу! — оборвал его Вадик. — Вот например, задачка. Вы знаете, что такое расстояние Хэмминга между двумя строками равной длины?
— Да, это количество индексов, в которых символы этих строк не равны.
— Верно. Определим расстояние от шаблона p до строки s как суммарное расстояние Хэмминга от p до всех подстрок s, имеющих длину |p|. В строке и в шаблоне некоторые символы стёрты. Нужно восстановить стёртые символы так, чтобы расстояние от p до s было минимально возможным.

Исходные данные

В первой строке дана строка s, во второй — шаблон p. Обе строки непусты, имеют длину не более 1000 и состоят из символов «0», «1» и «?». «?» обозначает стёртые символы, которые нужно восстановить. Длина p не превосходит длины s.

Результат

В первой строке выведите минимальное расстояние от p до s после восстановления всех стёртых символов. Во второй и третьей строках соответственно выведите s и p, в которых символы «?» заменены на «0» и «1».

Пример

исходные данныерезультат
00?
1?
2
000
10
Автор задачи: Михаил Рубинчик
Источник задачи: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1851. GOV-стажировка