Make a Number
Time limit1.5sMemory limit1024 MB
Find the minimum cost to turn A into B using single-digit changes (cost is the digit gap) or adding an integer y (cost |y|).
- Level
Medium6 of 10
- Topics
- Shortest path, Dynamic programming, Implementation
- Solved
- No attempts yet
Problem
Two positive integers are given.
You may apply the following two operations to in any order and any number of times.
- Let the decimal representation of be . That is, , where each is an integer with , and . Choose any integer () and any (), and replace with . If , then must hold. The cost of this operation is .
- Choose any integer with and add it to . The cost of this operation is .
For example, choosing and for the number 2024 and performing operation 1 once gives 2074. The cost of this operation is .
However, choosing and to get 0024, or choosing and to get 12024, is not allowed because it violates the conditions.
Also, choosing for the number 926 and performing operation 2 twice to get 0 is not allowed either.
What is the minimum total cost of turning into ?
Input
The first line contains two positive integers (), separated by a space.
Output
Print the minimum total cost of turning into .