In order to get the first 30 points, we just need to simulate the process and count the steps.
In order to get the next 60 points, we need something a bit smarter.
Suppose we start from a large number like 898325235. What is going to happen in the first steps of the solution? Obviously, there is going to be quite a long string of steps in which we repeatedly subtract 8. We are going to keep doing this until the leading digit finally changes from 8 to 7.
The key to a more efficient solution is to realize that we can count these steps and once we do that, we can perform all of them at once.
What is the number of steps in our example? It is the smallest \(x\) such that \(898\,325\,235 - 8x\) becomes smaller than \(800\,000\,000\). Clearly, \(x = 1 + \lfloor 98\,325\,235 / 8\rfloor\). (The integer division counts the steps that aren’t changing the leading digit, and then we add one for the step that does.)
The above solution + handling of big integers + waiting for a while should actually be enough to get the full 100 points, but we can get there faster by noticing that we are repeatedly doing a lot of fully identical calculations as we are processing various values of \(n\).
In particular, we can note the following:
Before reaching a single-digit number, the process will never skip a lead digit: subtracting a single digit \(d\) from the current \(n\) changes its value by less than 10, and this cannot skip an entire leading digit.
Once the leading digit is 1, we are going with a step of 1, and this means that we cannot skip any value and we’ll eventually reach some value of the form \(10^x\), and then in the next step the value \(10^x - 1\), i.e., the number formed by \(x\) nines.
The 90-point solution, started from any number, will also reach this last value. Hence, an easy way of speeding it up so that it computes all answers in the third subproblem quickly is to just cache a single answer: the answer to \(10^{19\,999} - 1\).
(There are alternate solutions that are even faster. E.g., we can realize that after simulating many steps in which we subtract the digit \(d\), the new number is just barely smaller than \(d\) times a power of 10, and we can cache the answers for all such numbers. But that just complicates the code and takes longer to implement properly.)
