← 返回题目列表

Codeforces · 1060/B

B. 最大数字和

中文机器翻译题面 查看原题

给你一个正整数$$$n$$$。

令 $$$S(x)$$$ 为 $$$x$$$ 以 10 为基数表示的数字总和,例如,$$$S(123) = 1 + 2 + 3 = 6$$$,$$$S(0) = 0$$$。

你的任务是找到两个整数 $$$a, b$$$,使得 $$$0 \leq a, b \leq n$$$, $$$a + b = n$$$ 和 $$$S(a) + S(b)$$$ 是所有此类对中最大的可能。

输入

输入的唯一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 10^{12})$$$。

输出

打印所有整数对 $$$a, b$$$ 中最大的 $$$S(a) + S(b)$$$,使得 $$$0 \leq a, b \leq n$$$ 和 $$$a + b = n$$$。

示例

输入 #1

35

输出 #1

17

输入 #2

10000000000

输出 #2

91

注意

在第一个示例中,您可以选择 $$$a = 17$$$ 和 $$$b = 18$$$,这样 $$$S(17) + S(18) = 1 + 7 + 1 + 8 = 17$$$。可见不可能得到更大的答案。

在第二个测试示例中,您可以选择 $$$a = 5000000001$$$ 和 $$$b = 4999999999$$$,其中 $$$S(5000000001) + S(4999999999) = 91$$$。可见不可能得到更大的答案。