Олимпиада проводится при поддержке Московского физико-технического института, Компьютерной компании НИКС, Компании Yandex
Информационная поддержка:
журнал "Мир ПК"
IV Открытая олимпиада школьников по программированию, 2009/10 учебный год
Задача K. Электронное табло
| Имя входного файла: | k.in |
| Имя выходного файла: | k.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Новый кодовый замок для владельцев нетбуков представляет головоломку не только для грабителей, но и для владельцев. На табло замка все время высвечивается некоторая комбинация нулей и единиц. Замок откроется, если на табло высветится некоторая определенная комбинация. Получить требуемую комбинацию из текущей можно нажимая в нужной последовательности кнопки, на которых написано 0 и 1 соответственно.
Если нажать кнопку с нулем, то текущая комбинация на табло сдвигается на одну позицию вправо (правая цифра при этом исчезает), а в самом левом разряде записывается 0. При нажатии на кнопку с единицей происходит то же самое, только в левый разряд записывается 1.
Известно, какая комбинация цифр сейчас находится на табло, и какую комбинацию требуется получить, чтобы открыть замок. Помогите владельцу нетбука - определите, за какое минимальное количество нажатий на кнопки можно получить требуемую комбинацию.
Формат входных данных
Первая строка содержит текущую последовательность цифр, вторая строка - последовательность, которую требуется получить. Гарантируется, что обе последовательности не пустые, имеют одинаковую длину, не превосходящую 100 000, и состоят только из нулей и единиц. Цифры в строках записаны подряд (без пробелов).
Формат выходных данных
Выведите минимальное количество нажатий на кнопки, с помощью которого можно решить поставленную задачу.
Примеры
| k.in | k.out |
1101 1011 |
2 |
0000 1111 |
4 |