UPD
Задача спрашивает, на самом деле, о максимальной сумме. Тут даже раскладывать на пары не надо:
def digits(n:int) -> list[int]:
if n == 0:
return [0]
res = []
while n > 0:
res.append(n%10)
n //=10
return res
def solve(n:int) -> int:
ndigs = digits(n)
s, ndigs = sum(ndigs), ndigs[:-1]
while len(ndigs) > 0 and ndigs[0] == 9:
ndigs = ndigs[1:]
return s + 9*len(ndigs)
Обоснование ниже в тексте
Смотрите, как можно разложить число 45:
- начинаем справа. Берём 5. Эту цифру можно получить из суммы маленьких чисел, например 2+3, а можно из суммы цифр побольше, например 7+8. В первом случае сумма цифр будет 5, а во втором 15.
- следующая цифра 4.
- Если мы раскладывали 5 на сумму малых, то переноса нет, и 4 надо разложить на сумму малых (так как это крайняя цифра) - 4 = 2+2. Получилось разложение 45 = 22+23, сумма цифр 9
- но если 5 разложили на сумму больших, то был перенос десятки в следующий разряд, и надо раскладывать цифру 3. Возмём, к примеру, 1+2. Получится 45 = 17+28, сумма цифр 18.
Идея понятна? Нужно начинать раскладывать справа, и каждый раз стараться разложить на сумму больших цифр, которые дадут перенос в следующий разряд. Так можно разложить все цифры, кроме 9. Девятка раскладывается только на сумму малых цифр (причём, что характерно, не важно каких именно - сумма всё равно будет 9).
То есть максимальная сумма цифр для разложения будет сумма цифр исходного числа плюс число возможных переносов, помноженное на 9. Например, 29 - сумма цифр 11. Переносов нет - первая цифра 9, вторая цифра 2 - конечная. Поэтому как ни раскладывай, в сумме будет 11 (11+18, 12+17, 13+16, 14+15). В числе 45 один возможный перенос - это первая цифра 5. Вторая цифра крайняя, переноса не будет. Поэтому максимальная сумма в разложении (4+5)+9 = 18. В числе 7019 нет переноса для единиц, там стоит 9, зато есть переносы для десятков и сотен, поэтому максимальная возможная сумма цифр (7+1+9)+2*9 = 35.
Кстати, переносы невозможны только для нескольких девяток подряд в младших разрядах, поэтому максимальную сумму можно посчитать без разложения:
- просуммировать цифры исходного числа (7019 -> 17)
- отбросить справа все девятки, идущие подряд (7019 -> 701)
- отбросить цифру слева (701->01)
- количество оставшихся цифр умножить на 9 и прибавить сумму цифр исходного числа (2*9 + 17 = 35)
Разложить можно разными способами. Я сделал разложение примерно пополам.
def digits(n:int):
"Генератор цифр числа, начиная с единиц"
while n > 0:
yield n%10
n = n // 10
def num(digits:list[int]) -> int:
"Строит число из списка цифр, начинающийся с единиц."
res = 0
for d in reversed(digits):
res = res*10+d
return res
def split(n:int) -> tuple[list[int],list[int]]:
"Возвращает два списка цифр, которые представляют числа `a` и `b` такие, что `a+b=n`"
n_digits = list(digits(n))
a, b, carry =[], [], 0
for d in n_digits[:-1]:
d = (d - carry + 10)%10
if d == 9:
a.append(5)
b.append(4)
else:
h1 = (10+d)//2
h2 = (10+d)-h1
a.append(h1)
b.append(h2)
carry = 1
d = n_digits[-1]
d = (d - carry + 10)%10
h1 = d//2
h2 = d-h1
a.append(h1)
b.append(h2)
return a,b
def solve(n:int) -> tuple[int, int, int]:
"""
Возвращает числа (а, b, s) такие что a+b=n, s - сумма цифр a и b.
"""
a,b = split(n)
return num(a), num(b), sum(a)+sum(b)
Проверка
def test(n):
a,b,s = solve(n)
print(f"{n} == {a} + {b} ({a+b}), сумма цифр {s}")
test(29)
test(45)
test(1140)
test(6699)
test(7019)
29 == 15 + 14 (29), сумма цифр 11
45 == 17 + 28 (45), сумма цифр 18
1140 == 565 + 575 (1140), сумма цифр 33
6699 == 2855 + 3844 (6699), сумма цифр 39
7019 == 3555 + 3464 (7019), сумма цифр 35