给定一个正整数 NN 。你可以对 NN 的任意一位数字执行任意次以下 2 种操 作： 将该位数字加 1 。如果该位数字已经是 9 , 加 1 之后变成 0 。 将该位数字减 1 。如果该位数字已经

是 0 , 减 1 之后变成 9 。

你需要通过执行上述操作，使得 NN 的各位数字之和最大化。请你输出最大的数字和。

输入格式
输入一个正整数 NN 。

输出格式
输出一个正整数，表示 NN 的各位数字之和最大值。

数据范围
1≤N≤10181≤N≤1018

输入样例1：
10
输出样例1：
10
输入样例2：
128
输出样例2：
20
输入样例3：
358
输出样例3：
27
输入样例4：
987654321
输出样例4：
81

分析

1.将数字N分解成各个位上的数字，存到数组c中

2.从高位到低位遍历数组c，对于每个c[i]进行以下操作：

如果c[i]<=4, 则将c[i]加到sum中
如果c[i]>4, 且i!=0, 则将sum+10^(i-1)加到sum中
如果c[i]>4, 且i==0, 则将sum+1加到sum中

3.输出sum

时间复杂度 O(lgn)

相关问题

给定一个正整数 NN，请你输出 NN 以内（不包含 NN）的质数以及质数的个数。

以下是 Python 代码：

def count_primes(n):
    if n < 2:
        return 0
    primes = [True] * n
    primes[0] = primes[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
    return sum(primes), [i for i in range(n) if primes[i]]

n = int(input())
count, primes = count_primes(n)
print(count)
print(*primes)

首先，定义一个函数 `count_primes(n)`，输入正整数 n，输出 n 以内的质数个数以及质数列表。这个函数使用了埃氏筛法，具体实现方法可以参考这篇博客：[埃氏筛法求素数](https://www.cnblogs.com/ECJTUACM-873284962/p/7654269.html)。

然后，读入正整数 n，调用 `count_primes(n)`，输出质数个数以及质数列表。其中，使用了 `print(*primes)` 将质数列表打散为多个参数输出。

给定一个正整数 NN，请你输出 NN 以内（不包含 NN）的质数以及质数的个数。python

代码如下：

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

n = int(input("请输入一个正整数: "))
count = 0
for i in range(2, n):
    if is_prime(i):
        count += 1
        print(i, end=" ")
print("\n质数的个数为:", count)

解释：

首先定义一个函数 `is_prime`，用于判断一个正整数是否为质数。如果 n 小于等于 1，则不是质数；如果 n 大于 1，就从 2 开始循环到 n 的平方根（包括平方根），判断 n 是否能被循环中的数整除。如果能整除，说明 n 不是质数，返回 False，否则返回 True。

然后输入一个正整数 n，定义一个计数器 count，从 2 开始循环到 n-1（不包括 n），判断循环中的数是否为质数。如果是，计数器加 1，并输出该数。最后输出质数的个数。

注意，这里用 `end=" "` 将输出的数用空格分隔开，方便观察。