Help me to understand this question
Pages: 12
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.
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.
You get given two numbers.
You can transform the first number into another number.
There are two ways you can do that transformation.
You have to make that first number as small as possible, by doing those transformations.
So do that. Make it as small as possible, in as few transformations as possible.
You can transform the first number into another number.
There are two ways you can do that transformation.
You have to make that first number as small as possible, by doing those transformations.
So do that. Make it as small as possible, in as few transformations as possible.
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.
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
yeah, we are definitely missing some corner cases.
Could anyone please drop a good input in order to debug the code
@maxdaen I am getting the same test cases wrong. Please someone gives us some edge cases.
any one getting task number 6 AC ??.. i am getting failed at that one task
@pplo123, Your answer for 95,83 is wrong. It should be 1,9 (add 83 6 times, add digits, add 83, add digits).
please can any one just give a hint on how should we start this question?I am not getting any kind of hint on how to do this question .Thanks.
Pages: 12