Tenkey
Time limit2sMemory limit512 MB
Find the minimum number of keypad operations (cursor moves plus key presses) to type a positive integer congruent to R modulo M, starting from the 0 key.
- Level
Hard9 of 10
- Topics
- Graph, BFS, Shortest path, Dynamic programming
- Solved
- No attempts yet
Problem
JOI has one numeric keypad. On this keypad, the keys printed with the digits 0 through 9 are arranged as in the figure below. Note that there is no key below the key printed with 2, nor below the key printed with 3.
The keypad also has a cursor that points at one of the keys on the keypad. Initially the cursor points at the key printed with 0.
In one operation, JOI can choose and perform one of the following.
- Move the cursor to a key that is adjacent, up, down, left, or right, to the key the cursor currently points at. However, the cursor cannot be moved to a position where no key exists.
- Press a key. That is, enter the digit printed on the key the cursor points at. If a digit has already been entered by a previous operation, the new digit is entered immediately to the right of the digits already entered.
JOI wants to use this keypad to enter a positive integer whose remainder when divided by M is R. Operating the keypad takes time, so he wants to enter it in as few operations as possible.
Given M and R, write a program to find the minimum number of operations JOI needs to perform.
Input
The input is given from standard input in the following format.
M R
Output
Print, on one line, the minimum number of operations needed to enter a positive integer whose remainder when divided by M is R.
Constraints
2 ≦ M ≦ 100 000.1 ≦ R ＜ M.- All input values are integers.