本文共 1622 字，大约阅读时间需要 5 分钟。

题目链接:

Time limit per test: 2 seconds Memory limit per test: 512 megabytes

Problem Description

You are given a positive integer n.

Let S(x) be sum of digits in base 10 representation of xx, for example, S(123)=1+2+3=6, S(0)=0. Your task is to find two integers a,ba,b, such that 0≤a,b≤n, a+b=n and S(a)+S(b) is the largest possible among all such pairs.

Input

The only line of input contains an integer n (1≤n≤10^12)

Output

Print largest S(a)+S(b) among all pairs of integers a,b, such that 0≤a,b≤n and a+b=n.

Input

35

10000000000

Output

17

91

Note

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.

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.

Solving Ideas

将n分离成最高项和其余项两项，然后把最高项的减一，另一项加一，使其出现最多的9。

例如: n=359=300+59=299+60, 则s(299)+s(60)=2+(3-1)*9+6+0=26; 其中(3-1)指的是最高位后有多少个9. n=99=90+9=89+10, 则s(89)+s(10)=8+(2-1)*9+1+0=18; n=2568=2000+568=1999+569, 则s(1999)+s(569)=1+(4-1)*9+5+6+9=48。 具体见代码:

#include 
   
    using namespace std;int main(){    char s[15];    int ans, len, c, t;    scanf("%d", &t);    while (t--) {        c = 1;        ans = 0;        scanf("%s", s);        len = strlen(s);        ans += s[0] - '0' + (len - 1) * 9 - 1;        for (int i = len - 1; i > 0; i--) {            s[i] += c;            c = (s[i] - '0') / 10;            s[i] = (s[i] - '0') % 10 + '0';            ans += s[i] - '0';        }        printf("%d\n", ans + c);    }    return 0;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/83029498 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！