Problem K
Keep Calm And Carry Off
A few weeks ago, she also learnt a simpler method of addition. In this method, you repeatedly add $1$ to one of the numbers and subtract $1$ from the other, until the second one reaches zero. This can of course take a lot of time for large numbers.
Petra now wants to combine the two methods, for fast and error-free addition. Her plan is to first perform the second method one step at a time, until the two numbers would not produce a carry digit when added using the standard algorithm (for positive integers, this always happens eventually). To evaluate the performance of her new method, she has asked you to help her compute the number of steps she must perform of the second method when adding two given integers. Petra may perform the addition by $1$ to either of the two numbers (and subtraction by $1$ from the other).
Input
The input consists of two lines, each containing a positive integer with at most $10^6$ digits. These are the two integers Petra wants to add.
Output
Output a single integer, the minimum number of times Petra must add $1$ to one of her numbers (while subtracting $1$ from the other) until they can be added using the standard addition algorithm without any carry digits.
Sample Input 1 | Sample Output 1 |
---|---|
10 99 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
90 10 |
10 |
Sample Input 3 | Sample Output 3 |
---|---|
23425 487915 |
12085 |