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