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

Уральская региональная командная олимпиада по программированию 2011

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

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

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Problem illustration
Недавно Вадику пришлось распрощаться с очередным игроком команды Team.GOV. Ему предстояло найти в команду нового игрока для участия в чемпионате Урала. Внезапно Вадик вспомнил, что на это соревнование допускаются сборные команды, а у него есть хорошая знакомая из Китая — Сяохун Хао, участница чемпионата мира про программированию. Отличный вариант! И вот он уже сидит за компьютером и строчит письмо.
Привет!
Я ищу игрока на чемпионат Урала. Не хочешь поиграть в команде Team.GOV? Если тебя интересует это предложение, вышли мне до завтра решение тестового задания.
Расстоянием Хэмминга между двумя строками равной длины называется количество символов, в которых различаются эти строки. Назовём расстоянием между строкой s1 и более короткой строкой s2 суммарное расстояние Хэмминга от строки s2 до всех подстрок строки s1, равных по длине строке s2. Будем называть строку частичной, если в ней помимо символов алфавита может встречаться символ «?». Даны две частичные строки, требуется заменить в них знаки вопроса на символы алфавита так, чтобы расстояние между полученными строками было минимальным.
Тебе нужно решить эту задачу для случая, когда первая строка циклическая. Удачи!
P.S. Ах да! Строка называется циклической, когда для неё помимо обычных подстрок определены подстроки, равные конкатенации некоторого суффикса и некоторого префикса. Например, обычная строка «abcd» имеет две подстроки длины 3: «abc» и «bcd». А циклическая строка «abcd» дополнительно к тем двум имеет ещё две подстроки длины 3: «cd» + «a» = «cda», «d» + «ab» = «dab».
Конечно же, Вадим из уважения к Сяохун сделал тесты, строки в которых записаны не латинскими буквами, а иероглифами.

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

Входные данные состоят из двух блоков. Первый блок данных описывает циклическую строку s, второй — строку t. В первой строке каждого блока находится целое число n — длина строки (1 ≤ n ≤ 100 000). Во второй строке блока записаны n целых неотрицательных чисел через пробел. Положительные числа обозначают иероглифы, а число 0 — знак вопроса. Числа, обозначающие иероглифы, не превосходят 100 000.

Результат

Замените в строках s и t знаки вопроса на иероглифы так, чтобы расстояние между полученными в результате этой замены строками было минимальным. Выведите искомое расстояние.

Пример

исходные данныерезультат
5
2 1 1 0 2
4
3 0 3 0
14

Замечания

Нужно заменить знак вопроса в строке s на третий иероглиф, а знаки вопроса в строке t — на первый и второй иероглифы соответственно. Циклическая строка «21132» имеет подстроки «2113», «1132», «1322», «3221» и «2211». Расстояние Хэмминга от строки «3132» до этих подстрок равно соответственно трём, одному, трём, трём и четырём. Суммарное расстояние между строками равно четырнадцати.
Автор задачи: Михаил Рубинчик
Источник задачи: Уральская региональная командная олимпиада по программированию 2011
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1879. GOV-стажировка 2