1157A.md (1346B)
1 Source: https://codeforces.com/problemset/problem/1157/A 2 3 A. Reachable Numbers 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Let's denote a function $f(x)$ in such a way: we add $1$ to $x$, then, while there is at least one trailing zero in the resulting number, we remove that zero. For example, 22 23 * $f(599) = 6$: $599 + 1 = 600 \rightarrow 60 \rightarrow 6$; 24 * $f(7) = 8$: $7 + 1 = 8$; 25 * $f(9) = 1$: $9 + 1 = 10 \rightarrow 1$; 26 * $f(10099) = 101$: $10099 + 1 = 10100 \rightarrow 1010 \rightarrow 101$. 27 28 We say that some number $y$ is reachable from $x$ if we can apply function $f$ to $x$ some (possibly zero) times so that we get $y$ as a result. For example, $102$ is reachable from $10098$ because $f(f(f(10098))) = f(f(10099)) = f(101) = 102$; and any number is reachable from itself. 29 30 You are given a number $n$; your task is to count how many different numbers are reachable from $n$. 31 32 Input 33 34 The first line contains one integer $n$ ($1 \le n \le 10^9$). 35 36 Output 37 38 Print one integer: the number of different numbers that are reachable from $n$. 39 40 Examples 41 42 Input 43 44 ``` 45 1098 46 ``` 47 48 Output 49 50 ``` 51 20 52 ``` 53 54 Input 55 56 ``` 57 10 58 ``` 59 60 Output 61 62 ``` 63 19 64 ``` 65 66 Note 67 68 The numbers that are reachable from $1098$ are: 69 70 $1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1098, 1099$.