Задача Кодовый замок (CODELOCK)
На золотохранилище дяди Скруджа недавно установили новый кодовый замок уникальной конструкции. Внешне он выглядит как кольцо, на которое надето 8 одинаковых барабанов с цифрами от 0 до 9, равномерно расположенных по кругу. На барабанах за цифрой i (0≤i≤8) следует цифра i+1, за цифрой 9 следует цифра 0.
Разрешается вращать только тот барабан, который в данный момент находится в верхней части кольца. При этом само кольцо можно поворачивать по часовой или против часовой стрелки так, чтобы разместить сверху другой барабан. Замок открывается только случае установки на барабанах определенной последовательность цифр.
За одну секунду дядя Скрудж может повернуть верхний барабан на одну позицию в любую сторону (то есть перейти к следующей или предыдущей цифре на этом барабане) или повернуть кольцо на один барабан по часовой или против часовой стрелки для смены барабана в верхней части кольца. Естественно, дядя Скрудж стремится попасть к своему золоту как можно быстрее, поэтому крайне заинтересован в том, чтобы открыть замок за минимальное количество операций. Ваша задача состоит в том, чтобы определить это количество.
Формат ввода/вывода:
Программа считывает из стандартного устройства ввода два набора по 8 цифр каждый. Между цифрами внутри набора нет разделителей, между наборами – пробел. Первый набор цифр показывает начальное положение барабанов, начиная с верхнего. Второй – положение барабанов (начиная с верхнего), которое открывает замок.
Программа должна вывести на стандартное устройство вывода одно число – минимально возможное количество операций, необходимых для открытия замка. Если получить второе число из первого невозможно, вывести число −1.
Пример:
|
ввод |
вывод |
|
12345678 23456789 |
3 |
|
12345678 11111111 |
29 |