1060B.md (1196B)
1 Source: https://codeforces.com/problemset/problem/1060/B 2 3 B. Maximum Sum of Digits 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a positive integer $n$. 22 23 Let $S(x)$ be sum of digits in base 10 representation of $x$, for example, $S(123) = 1 + 2 + 3 = 6$, $S(0) = 0$. 24 25 Your task is to find two integers $a, b$, such that $0 \leq a, b \leq n$, $a + b = n$ and $S(a) + S(b)$ is the largest possible among all such pairs. 26 27 Input 28 29 The only line of input contains an integer $n$ $(1 \leq n \leq 10^{12})$. 30 31 Output 32 33 Print largest $S(a) + S(b)$ among all pairs of integers $a, b$, such that $0 \leq a, b \leq n$ and $a + b = n$. 34 35 Examples 36 37 Input 38 39 ``` 40 35 41 ``` 42 43 Output 44 45 ``` 46 17 47 ``` 48 49 Input 50 51 ``` 52 10000000000 53 ``` 54 55 Output 56 57 ``` 58 91 59 ``` 60 61 Note 62 63 In the first example, you can choose, for example, $a = 17$ and $b = 18$, so that $S(17) + S(18) = 1 + 7 + 1 + 8 = 17$. It can be shown that it is impossible to get a larger answer. 64 65 In the second test example, you can choose, for example, $a = 5000000001$ and $b = 4999999999$, with $S(5000000001) + S(4999999999) = 91$. It can be shown that it is impossible to get a larger answer.