codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.