Beautiful Numbers

Research note. I checked the official statement, the Educational Codeforces Round 187 editorial page, which currently exposes the reference solution more than prose, a Codeforces accepted-status page, and a public implementation for the same problem at GitHub. The supplied statement is canonical; these sources just confirm the greedy direction and the leading-digit edge case.

Let $S=F(x)$ be the digit sum of the current number. The beauty condition is

$F(F(x))=F(x),$

so it is really asking when $F(S)=S$.

For every $1\le S\le 9$, $S$ is one digit, so $F(S)=S$. For every $S\ge 10$, the digit sum is strictly smaller than the number itself, so $F(S)<S$. Therefore a number is beautiful exactly when its digit sum is between $1$ and $9$. That is the whole trick; the scary-looking double $F$ is just a fake mustache.

If the original digit sum $S\le 9$, we are already done and the answer is $0$.

Now assume $S>9$. We need to reduce the digit sum to at most $9$, so the needed reduction is

$R=S-9.$

Consider one digit. If it is not the leading digit and its value is $d$, we can change it to $0$, reducing the sum by at most $d$. If it is the leading digit, we cannot change it to $0$, so the smallest allowed value is $1$, and the maximum reduction is $d-1$.

So each digit has a capacity:

$c_i=d_i-[i=0].$

Changing digit $i$ can contribute any reduction from $0$ up to $c_i$, as long as we pick the replacement digit accordingly.

Now the problem is: what is the minimum number of capacities whose total can cover $R$?

The greedy answer is to sort capacities descending and take the biggest ones first.

Why is this optimal? For any fixed number of moves $k$, the maximum possible digit-sum reduction is the sum of the $k$ largest capacities. No other set of $k$ digits can do better. Therefore, if the $k$ largest capacities sum to less than $R$, then $k$ moves are impossible. The first $k$ where their sum reaches at least $R$ is also achievable: reduce the first $k-1$ chosen digits as much as possible, then reduce the last chosen digit by exactly the remaining amount. Since the previous $k-1$ were not enough, that remaining amount is positive and at most the last digit's capacity.

The final digit sum can be made exactly $9$, so it is beautiful. No overshooting drama needed.

Edge cases:

• A one-digit number is always already beautiful.
• The leading digit contributes only $d-1$, not $d$.
• A leading digit equal to $1$ has capacity $0$.
• Reading $x$ as a string is clean and avoids caring about the exact integer width.

Complexity per test case is $O(n\log n)$ for sorting the digits, where $n\le 19$. Memory is $O(n)$.