Problem A
Combinations
Ivan is often late to class in the morning. However, rather than, say, setting his alarm a bit earlier, he has decided the solution to the problem is to micro-optimize his morning routine. Getting dressed now takes only 48 seconds (since he sleeps in his clothes) and breakfast is down to 4.3 minutes. Despite these optimizations, he is still routinely late, so he has turned his attention to optimizing the time it takes to unlock his bike.
Ivan has a combination lock consisting of a sequence of four rings; each ring contains all the digits from 0 to 9 in order and can be turned to any digit. Turning past 9 goes back around to 0, and vice versa.
The lock starts in a certain state, corresponding to a sequence of digits, and Ivan wants to get it to a certain target state as fast as possible. One strategy would be to individually turn each ring forward until the target digit for that ring is reached. However, it may sometimes be faster to turn a ring backwards instead of forwards. In addition, any consecutive sequence of rings can be turned all at once, which can also save time. Formally, a single step is defined as turning any consecutive sequence of rings all forward by one digit, or all backward by one digit.
Input
There are exactly two lines of input. Each line contains a sequence of four digits, with each digit in the range $0$–$9$. The first line specifies the starting state of the lock, and the second line specifies the target state.
Output
Output the fewest number of steps Ivan needs to transform the starting state into the target state.
| Sample Input 1 | Sample Output 1 |
|---|---|
1134 3963 |
8 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1582 1692 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
0000 1234 |
4 |
