Here's an alternative solution to today's Educational Round problem F.

Observe (through trying $$$n \le 10^5, n \le 10^6$$$, etc) that the number of answers is "not too large".

Check offline that the answer for $$$n = 10^9 - 2$$$ is smaller than $$$600000$$$.

We say an integer is a founder if $$$S(n) \neq S(i)$$$ for all $$$1 \le i \le n-1$$$.

Observe that many of the founders are numerically close to each other.

This gives rise to the following algorithm: generate a sequence of $$$D$$$ segments $$$[l_i,r_i]$$$ using a greedy algorithm such that this sequence of segments includes all the founders and $$$r_i-l_i \le C$$$. Hardcode all the segments into the submission.

Then it takes $$$O(CD \times \text{constant})$$$ time to check the candidate founders, after which we will find all the founders.

Choose $$$C=1000$$$ to obtain around $$$D=8000$$$ segments, unfortunately that is too much for Codeforces to handle (the number of characters cannot exceed 65535 in a submission). Choose $$$C=10000$$$ to obtain around $$$D=3000$$$ segments and it works.

Submission: 317636794