You are given positive integers N and D. You may perform operations of the following two types:
1- add D to N, i.e. change N to N+D
2- change N to digitsum(N)
Here, digitsum(x) is the sum of decimal digits of x. For example, digitsum(123)=1+2+3=6 and digitsum(100)=1+0+0=1.
You may perform any number of operations (including zero) in any order. Please find the minimum obtainable value of N and the minimum number of operations required to obtain this value.
Example Input
3
2 1
9 3
11 13
Example Output
1 9
3 2
1 4
Explanation
Example case 1: The value N=1 can be achieved by 8 successive "add" operations (changing N to 10) and one "digit-sum" operation.
Why would your algorithm give the minimum value of N? Why would it give the minimum number of steps to achieve N? If I say that step 2 should loop 9455 times instead of 10^4, then would I be right or wrong? Why? What if I said that the number is N2-4D/3?
You need to think about the algorithm and the steps. Don't worry about the code until you're sure about the algorithm. After all, there's no point in committing an algorithm to code when you don't know what the algorithm is.
@Repeater I had figured out the algorithm but some test cases are showing WA. I'm quite sure I am missing some boundary cases. Can you give me some edge cases to debug my code?
@pplo123, same here mate, im getting one WA in subtask 1, and three WA in subtask 2.
yeah, we are definitely missing some corner cases.
Could anyone please drop a good input in order to debug the code