Задача Кодовий замок (CODELOCK)

На скарбницю із золотом дядька Скруджа недавно встановили новий кодовий замок унікальної конструкції. Зовні він виглядає як кільце, на якому розміщено 8 однакових барабанів з цифрами від 0 до 9, що рівномірно розташовані по колу. На барабанах за цифрою i (0≤i≤8) розміщена цифра i+1, за цифрою 9 наступною є цифра 0.

Дозволяється обертати тільки той барабан, який в даний момент знаходиться у верхній частині кільця. При цьому саме кільце можна повертати за годинниковою або проти годинникової стрілки таким чином, щоб розмістити зверху інший барабан. Замок відкривається тільки у випадку встановлення на барабанах певної послідовності цифр.

За одну секунду дядя Скрудж може повернути верхній барабан на одну позицію в будь-яку сторону (тобто перейти до наступної або попередньої цифри на цьому барабані) або повернути кільце на один барабан за годинниковою або проти годинникової стрілки для зміни барабана у верхній частині кільця. Зазвичай, дядя Скрудж прагне попасти до свого золота якомога швидше, а тому він зацікавлений відкрити замок за найменшу кількість операцій. Ваша задача полягає у тому, щоб визначити цю кількість операцій.

Формат введення/виведення:

Програма зчитує зі стандартного пристрою введення два набори по 8 цифр кожен. Між цифрами всередині набору немає розділювачів, між наборами – пропуск. Перший набір цифр показує початкове положення барабанів, починаючи з верхнього. Другий – положення барабанів (починаючи з верхнього), яке відкриває замок.

Програма повинна вивести на стандартний пристрій виведення одне число – мінімально можливу кількість операцій, що необхідні для відкриття замка. Якщо отримати друге число з першого неможливо, вивести число −1.

Приклад:

Введення

Виведення

12345678 23456789

3

12345678 11111111

29

© LIKT 1998-2018