Problem:


Score : 300 points

Problem Statement

Find the maximum possible sum of the digits (in base 10) of a positive integer not greater than N.

Constraints

1\leq N \leq 10^{16}

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

Print the maximum possible sum of the digits (in base 10) of a positive integer not greater than N.

Sample Input 1

100

Sample Output 1

18

For example, the sum of the digits in 99 is 18, which turns out to be the maximum value.

Sample Input 2

9995

Sample Output 2

35

For example, the sum of the digits in 9989 is 35, which turns out to be the maximum value.

Sample Input 3

3141592653589793

Sample Output 3

137



Sample input:
100


Sample output:
18

Submission status: Accepted

Solution code:
S = input()
keta = len(S)

chk = True
for i in range(keta-1):
    if S[i+1] != '9':
        chk = False
        break

if chk:
    ans = 9 * (keta-1) + int(S[0])
else:
    ans = 9 * (keta-1) + int(S[0]) - 1

print(ans)

Submission status: Accepted

Solution code:
s=input()
flag=True
for i in range(1,len(s)):
    if s[i]!="9":
        flag=False
if flag:
    print((len(s)-1)*9+int(s[0]))
else:
    print((len(s)-1)*9+int(s[0])-1)

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    mt = 0
    for i in range(len(str(n))):
        t = (n // (10 ** i)) * (10 ** i)
        t -= 1 if i != 0 else 0
        t = str(t)
        tt = 0
        for j in range(len(t)):
            tt += int(t[j])
        mt = max(mt, tt)
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = list(map(int, list(input())))

if len(n) == 1:
    print(n[0])
elif n[0] == 9:
    print(max(sum(n), 9 * len(n) - 1))
elif n[1] == 9:
    print(max(sum(n), n[0] + 9 * len(n) - 10))
else:
    print(max(sum(n), n[0] + 9 * len(n) - 10))

Submission status: Accepted

Solution code:
from sys import stdin

s = stdin.readline().rstrip()

if len(s) == 1:
    print(int(s))
    exit()

if s == "9"*len(s):
    print(9*len(s))
else:
    if s[1:] == "9"*(len(s)-1):
        print(int(s[0])+9*(len(s)-1))
    else:
        print(int(s[0])-1+9*(len(s)-1))

Submission status: Accepted

Solution code:
in_list = list(map(int, list(str(input()))))

ans = 9 * (len(in_list) - 1) + in_list[0] - 1 # 先頭の位の数を一つ下げて、他が全部9が最大のはず
print(max(ans, sum(in_list)))

Submission status: Accepted

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    s = str(readline().rstrip().decode('utf-8'))
    mt = 0
    for i in range(len(s)):
        tt = ""
        t = 0
        if i != 0:
            m = 10 ** i
            tt = str(int(s) // m * m - 1)
            t = 0
        else:
            tt = s
        for j in range(len(tt)):
            t += int(tt[j])
        mt = max(mt, t)
    print(mt)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=input()
l=len(n)
dp=[[0,0] for i in range(l)]
dp[0][1]=int(n[0])
dp[0][0]=int(n[0])-1
for i in range(1,l):
  t=int(n[i])
  if t>0:dp[i][0]=max(dp[i-1][0]+9,dp[i-1][1]+t-1)
  else:dp[i][0]=dp[i-1][0]+9
  dp[i][1]=dp[i-1][1]+t
print(max(dp[l-1][0],dp[l-1][1]))

Submission status: Accepted

Solution code:
n=int(input())
ans=0
if n<10:
  ans=n
else:
  k=1
  while n>9:
    if n%10!=9:
      k=0
    ans+=9
    n//=10
  if k:
    ans+=n
  else:
    ans+=n-1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from functools import lru_cache

@lru_cache()
def F(N):
  if N < 10:
    return N
  q,r = divmod(N, 10)
  x1 = F(q) + r
  x2 = F(q-1) + 9
  return max(x1, x2)

answer = F(int(input()))
print(answer)

Submission status: Accepted

Solution code:
N = list(i for i in input())
L = len(N)

if L == 1:
  answer = int(N[0])
else:
  if N[0] == '9' and len(set(N)) == 1:
    answer = 9*L
  else:
    if N[0] != '9' and '9' in N and len(set(N)) == 2:
      answer = 9*(L-1) + int(N[0])
    else:
      answer = 9*(L-1) + int(N[0]) - 1

print(answer)

Submission status: Accepted

Solution code:
n = str(input())
if n == "1":
    print(1)
    exit()
if n[0] == "1":
    tmpint = eval("9"*(len(n)-1))
    #print("tmpint",tmpint)
else:
    tmpint = eval(str(eval(n[0])-1) + "9"*(len(n)-1))
    #print("tmpint",tmpint)
tmpsum = sum([
        eval(str(tmpint)[i]) for i in range(len(str(tmpint)))
    ])
ssum = sum([
        eval(n[i]) for i in range(len(str(n)))
    ])
print(max(tmpsum,ssum))
#print(tmpsum,ssum)

Submission status: Accepted

Solution code:
n=input()
if len(n)==1:
  print(n)
elif n[1]=="9" and len(set(n[1:]))==1:
  print(int(n[0])+(len(n)-1)*9)
else:
  print(int(n[0])-1+9*(len(n)-1))

Submission status: Accepted

Solution code:
n = input()
c = 0
for i in n:
  c += int(i)
print(max(c, int(n[0])-1 + 9*(len(n)-1)))

Submission status: Accepted

Solution code:
N = input()
L = len(N)

C = [sum(list(map(int,N)))]

for i in range(1,L):
    if N[-1-i] != '0':
        c = N[:-1-i]+str(int(N[-1-i])-1)+str(9)*i
        C.append(sum(list(map(int,c))))
        
print(max(C))

Submission status: Accepted

Solution code:
N = input()
lenN = len(N)
if len(N) == 1:print(N)
else:
  if len(N[1:].replace('9',''))==0:print(int(N[0])+9*(lenN-1))
  else:print(9*(lenN-1)+(int(N[0])-1))

Submission status: Accepted

Solution code:
n=input();print(int(n[0])-1*(len(n)>1)*(n[1:]!="9"*(len(n)-1))+9*(len(n)-1))

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = sys.stdin.buffer.readline().decode().rstrip()


# if int(N) < 10:
#     print(int(N))
#     exit()

def count(s):
    return sum(map(int, list(s)))


ans = count(N)
for i in range(len(N)):
    if N[i] != '0':
        a = count(N[:i]) + count(N[i]) - 1 + count('9' * (len(N) - i - 1))
        ans = max(ans, a)
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

s = rs()
a = int(s[0]) - 1 + 9 * (len(s) - 1)
b = sum(map(int, s))
print(max(a, b))

Submission status: Accepted

Solution code:
n = list(map(int,input()))

if len(n) == 1:
    print(n[0])
    exit()

if n[1:].count(9) == len(n) -1:
    print(n[0] + (len(n)-1)*9)
else:
    print(n[0]-1 + (len(n)-1)*9)

Submission status: Accepted

Solution code:
# AGC021
N = input()
ans_1 = 0
ans_2 = 0
for i in range(len(N)):
    ans_1 += int(N[i])
ans_2 = int(N[0]) - 1 + 9 * (len(N) - 1)
print(max(ans_1, ans_2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

N = int(input().split()[0])
n_list = [int(char) for char in str(N)]

if n_list[0] == 1 and N % 10 == 0:
    ans = 9 * len(n_list[1:])
else:
    total_1 = sum(n_list)
    n_list_2 = n_list[:]
    target_idx = -1
    for i, n in enumerate(n_list):
        if n == 9:
            continue
        else:
            if n != 0:
                target_idx = i
            break
    if target_idx != -1:
        if target_idx == 0:
            n_list_2[0] = n_list[0] - 1
            if len(n_list) > 2:
                n_list_2[1:] = [9] * len(n_list_2[1:])
        else:
            n_list_2[target_idx - 1] = n_list[target_idx - 1] - 1
            n_list_2[target_idx:] = [9] * len(n_list_2[target_idx:])
    total_2 = sum(n_list_2)
    ans = max(total_2, total_1)

print(ans)

Submission status: Accepted

Solution code:
N = input()
K = len(N)
ans = 0
flg = True
for i in range(1,K):
  if N[i] != "9":
    flg = False
    break
print(int(N[0]) + 9 * (K - 1) if flg else int(N[0]) + 9 * (K - 1) - 1)

Submission status: Accepted

Solution code:
N = list(input())
ans = 0
if len(N) == 1:
  print(*N)
  exit()
for i in range(len(N)):
  if i == 0 and N[i] != "9" and N[i+1] == "9":
    ans += int(N[i])
  elif N[i] != "9":
    N[i] = int(N[i]) - 1
    ans += N[i]
    ans += (len(N) - (i + 1)) * 9
    print(ans)
    exit()
  else:
    if i < len(N)-1 and N[i+1] != "9":
      ans += int(N[i]) - 1
      ans += (len(N) - (i + 1)) * 9
      print(ans)
      exit()
    else:
      ans += 9
print(ans)

Submission status: Accepted

Solution code:
N = input()
tmp1 = 0
tmp2 = 0

for i in range(len(N)):
    tmp1 += int(N[i])

tmp2 += int(N[0]) - 1
for i in range(len(N) - 1):
    tmp2 += 9

print(max(tmp1, tmp2))

Submission status: Accepted

Solution code:
N = int(input()) + 1
k = len(str(N)) - 1
print(9*k + N//(10**k) - 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = list(map(int, list(input())[: -1]))
dp = [0] * (len(N) + 1)
dp2 = [0] * (len(N) + 1)
#print(sum(N))
dp2[1] = max(N[0] - 1, 0)
for i in range(len(N)):
  dp[i + 1] = N[i] + dp[i]
  if i > 0:
    dp2[i + 1] = dp2[i] + 9
    if N[i] > 0: dp2[i + 1] = max(dp[i] + N[i] - 1, dp2[i + 1])
print(max(max(dp), max(dp2)))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = str(N)
    digit = len(S)
    if digit == 1:
        return print(N)
    if S[1] == '9':
        ans = (S[0] + S[1] + '9'*(digit - 2))
        if int(ans) > N:
            ans = int(ans) - 10**(digit - 1)
            ans = str(ans)
    else:
        ans = (str(int(S[0]) - 1) + '9' + '9'*(digit - 2))

    ans_sum = 0
    for a in ans:
        ans_sum += int(a)
    print(ans_sum)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=str(input())

def solve(n):
  res=0
  if len(n)==1:
    return n
  v=n[0]
  p=int(n[0])
  for i in range(len(n)-1):
    v+='9'
    p+=9
  if v==n:
    return p
  for i in range(len(n)):
    if i==0:
      res+=int(n[0])-1
    else:
      res+=9
  return res
  
print(solve(n))

Submission status: Accepted

Solution code:
def main():
    n = input()

    l = len(n)

    nines = "0" + "9" * (l - 1)
    nines = int(nines)

    num = nines
    for i in range(1, 10):
        tmp = i * 10 ** (l - 1) + nines
        if tmp <= int(n):
            num = tmp

    ans = sum(map(int, str(num)))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heapify,heappop,heappush
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def check(s):
    for i in range(len(s)):
        if s[i] != '9':
            return False
    return True

s = input()
n = len(s)
res = 0
if check(s[1:]):
    for i in s:
        res += int(i)
else:
    for i,t in enumerate(s):
        if i == 0:
            res += int(t) - 1
            continue
        res += 9

print(res)

Submission status: Accepted

Solution code:
n = input()

if n[1:] == '9'*(len(n)-1):
    print(int(n[0]) + 9*(len(n)-1))
else:
    print(int(n[0]) + 9*(len(n)-1)-1)

Submission status: Accepted

Solution code:
n = input()
ans = 0
for i in range(len(n)):
    ans += int(n[i])
sum = 0
for i in range(len(n)):
    if i == 0:
        if n[0] != 1:
            sum += int(n[i]) - 1
    else:
        sum += 9
ans = max(ans, sum)
print(ans)

Submission status: Accepted

Solution code:
N = input()

dp = [[ [0] * 10 for i in range(len(N)) ] for j in range(2) ]

ans = 0

for i in range(len(N)): #kai

    for j in range(2): #flag

        for k in range(10): # num

            if i == 0:
                if k < int(N[i]):
                    dp[1][i][k] = k
                elif k == int(N[i]):
                    dp[0][i][k] = k

            else:

                if j == 0 and k == int(N[i]):
                    dp[0][i][k] = max(dp[0][i][k],max(dp[0][i-1]) + k)

                elif j == 0 and k < int(N[i]):
                    dp[1][i][k] = max(dp[1][i][k],max(dp[0][i-1]) + k)

                elif j == 1:
                    dp[1][i][k] = max(dp[1][i][k],max(dp[1][i-1]) + k)

print (max( max(dp[0][len(N)-1]) , max(dp[1][len(N)-1]) )  )

Submission status: Accepted

Solution code:
n = input()
d=len(n)
if d==1:
    print(n)
elif n[0]!="9":
    if n[1:]=="9"*(d-1):
         ans=int(n[0])+int(9*(d-1))
    else:
        ans=int(n[0])-1+int(9*(d-1))
    print(ans)
else:
    if n=="9"*d:
        print(9*d)
    else:
        print(9*(d-1) +8)

Submission status: Accepted

Solution code:
N = input()
l = len(N)

n = 0
k = l - 1
for i in range(l):
    if N[i] != '9':
        k = i
        break

if k == 0:
    if N[1:] == '9' * (l - 1):
        n = int(N[0]) + 9 * (l - 1)
    elif N[0] == '1':
        n = (l - 1) * 9
    else:
        n = (int(N[0]) - 1) + (l - 1) * 9
else:
    if N == '9' * l:
        n = 9 * l
    else:
        n = (k - 1) * 9 + 8 + 9 + (l - k - 1) * 9

print(n)

Submission status: Accepted

Solution code:
n = input()

if len(n) == 1:
    print(n)
elif n[1:] == '9'*(len(n)-1):
    print(9*(len(n)-1) + int(n[0]))
else:
    print(9*(len(n)-1) + int(n[0])-1)

Submission status: Accepted

Solution code:
N = str(input())
K = len(N)
c = int(N[0])
for i in N[1:]:
    if i!="9":
        print(c+9*(K-1)-1)
        exit()
print(c+9*(K-1))

Submission status: Accepted

Solution code:
N=input()

if len(N)==1:
    print(N)
    exit()

def calc(str):
    l=list(map(int,str))
    all=sum(l)
    
    return all

cand1=str(int(N)-int(N[-1])-1)
cand2=str(int(N[0])*10**(len(N)-1)-1)

print(max(calc(cand1),calc(cand2),calc(N)))

Submission status: Accepted

Solution code:
def d(n):
    d=1
    while n>=10:
        d+=1
        n//=10
    return d

def top(n):
    return n//(10**(d(n)-1))

def isalmostall9(n):
    return n+1==(top(n)+1)*(10**(d(n)-1))

N=int(input())
if isalmostall9(N):
    ans=top(N)+9*(d(N)-1)
else:
    ans=top(N)-1+9*(d(N)-1)

print(ans)

Submission status: Accepted

Solution code:
n = input()

default_sum = sum([int(i) for i in n])

if len(n) == 1:
    print(n)
else:
    print(max(int(n[0]) - 1 + 9 * (len(n)-1), default_sum))

Submission status: Accepted

Solution code:
n = int(input())
print(int(str(n+1)[0])-1 + 9 * (len(str(n+1))-1))

Submission status: Accepted

Solution code:
n=int(input())
if n < 10 :
    print(n)
else:
    n=list(str(n))
    key=0
    for i in range(len(n)-1):
        if n[1+i]!="9":
            key=1
    if key ==0:
        print((len(n)-1)*9+int(n[0]))
    else:
        print((len(n)-1)*9+int(n[0])-1)

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    ns = str(n)
    ln = len(ns)
    left = int(ns[0])
    c1 = int(str(left) + "9" * (ln - 1))
    c2 = int(str(left - 1) + "9" * (ln - 1))
    if c1 <= int(n):
        print(sum([int(ci) for ci in str(c1)]))
    else:
        print(sum([int(ci) for ci in str(c2)]))


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
s = str(n)
len_s = len(s)

dp = [[0]*(len_s+1) for i in range(2)]

dp[0][1] = int(s[0])
dp[1][1] = int(s[0]) - 1

for i in range(1, len_s):
    for num in range(int(s[i]) + 1):
        dp[0][i+1] = max(dp[0][i+1], dp[0][i] + num)
        
    for num in range(int(s[i])):
        dp[1][i+1] = max(dp[1][i+1], dp[0][i] + num)
    
    for num in range(10):
        dp[1][i+1] = max(dp[1][i+1], dp[1][i] + num)

print(max(dp[0][len_s], dp[1][len_s]))

Submission status: Accepted

Solution code:
n = int(input())
s = str(n)
len_s = len(s)

ans = 0

for i in range(10):
    char = str(i)
    for i in range(len_s):
        num = i*"9" + char + (len_s-i-1)*"9"
        if int(num) <= n:
            tmp = sum([int(i) for i in num])
            ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
n=input()
q=n[0]
if len(n)==1:
	print(q)
	exit()
if n[0]=="1":
	for i in range(len(n)-1):
		if n[i+1]!="9":
			print(9*(len(n)-1))
			exit()
	print(1+9*(len(n)-1))
else:
	for i in range(len(n)-1):
		if n[i+1]!="9":
			print(int(n[0])-1+9*(len(n)-1))
			exit()
	print(int(n[0])+9*(len(n)-1))

Submission status: Accepted

Solution code:
#A問題
N = int(input())
S = list(str(N))
Slen = len(S)
s = int(S[0])
ans = 0
if N == (s+1)*(10**(Slen-1))-1:
    for ss in S:
        ans+=int(ss)
else:
    for i in range(Slen):
        if i == 0:
            ans+=(int(S[0])-1)
        else:
            ans+=9
            
print(ans)

Submission status: Accepted

Solution code:
n = input()
for i in n[1:]:
    if i != "9":
        print(int(n[0]) - 1 + (len(n) - 1) * 9)
        exit()
print(int(n[0]) + (len(n) - 1) * 9)

Submission status: Accepted

Solution code:
N = list(input())
num_1 = 0
num_2 = 0

for i in range(len(N)):
    if i == 0:
        num_1 += int(N[i]) - 1
    else:
        num_1 += 9

for n in N:
    num_2 += int(n)

print(max(num_1, num_2))

Submission status: Accepted

Solution code:
def solve(n):
    best = 0
    ans = 0
    for i in range(20):
        for d in range(9, -1, -1):
            v = best + d * (10**i)
            if v <= n:
                best = v
                ans += d
                break
    return ans

assert solve(100) == 18
assert solve(9995) == 35
assert solve(3141592653589793) == 137

n = int(input())
print(solve(n))

Submission status: Accepted

Solution code:
N=input();print(max(int(N[0])-1+9*(len(N)-1),sum(map(int,N))))

Submission status: Accepted

Solution code:
S=input()
N=int(S)
M=len(S)

if S[1:]=="9"*(M-1):
  print(sum(map(int,list(S))))
else:
  ans=sum(map(int,list(str(int(S[0])-1)+"9"*(M-1))))
  print(ans)

Submission status: Accepted

Solution code:
N =  int(input())

if N < 10:
    print(N)
    exit()

def digitSum(n):
    return sum([int(a) for a in str(n)])

ans = max(digitSum(10**(len(str(N)) - 1) - 1) + int(str(N)[0]) - 1, digitSum(N))
print(ans)

Submission status: Accepted

Solution code:
N = list(map(int, list(input())))
n = len(N)
if (n - 1) * 9 + N[0] == sum(N):
	print(sum(N))
else:
	print((n - 1) * 9 + N[0] - 1)

Submission status: Accepted

Solution code:
N=input()

t=0
for i in N:
	t+=int(i)

s=int(N[0])-1
s+=9*(len(N)-1)

print(max(s,t))

Submission status: Accepted

Solution code:
N = input()
if len(N) == 1:
    print(int(N))
    exit()

for c in N[1:]:
    if c != "9":
        print(int(N[0]) - 1 + (len(N) - 1) * 9)
        exit()
print(int(N[0]) + (len(N) - 1) * 9)

Submission status: Accepted

Solution code:
N=list(map(int,input()))
L=len(N)

ans1=9*(L-1)+N[0]-1

for i in range(L-1):
    if N[i]>N[i+1]:
        N[i]=N[i]-1
        for j in range(i+1,L):
            N[j]=9
        break

ans2=sum(N)

print(max(ans1,ans2))

Submission status: Accepted

Solution code:
def main():
    N = input().strip()
    all_nine = True
    for i in range(1, len(N)):
        if N[i] != "9":
            all_nine = False
    ans = int(N[0]) + 9 * (len(N) - 1)
    if all_nine:
        print(ans)
    else:
        print(ans - 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = input()
if len(n) == 1:
  print(int(n))
else:
  all9flg = True
  for i in range(1, len(n)):
    if n[i] != "9":
      all9flg = False
  if all9flg:
    print(9 * (len(n) - 1) + int(n[0]))
  else:
    print(9 * (len(n) - 1) + int(n[0]) - 1)

Submission status: Accepted

Solution code:
sN = input()
N = int(sN)
n = len(sN)
d = N//(10**(n-1))
if N == (d+1)*(10**(n-1))-1:
  r = d+9*(n-1)
else:
  r = d-1+9*(n-1)
print(r)

Submission status: Accepted

Solution code:
N = (input())
l = len(N)
top =int( N[0])
minus = 1
if l == 1:
    minus = 0

a1 = (l - 1 ) * 9 + (top - minus)
a2 = sum(map(int,list(N)))
print (max(a1,a2))

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, str(n)))[::-1]

def rec(s, keta):
    global ans
    if keta == -1:
        ans = max(ans, s)
        return

    rec(s+l[keta], keta-1)
    if l[keta]:
        tmp = s + l[keta]-1 + 9*keta
        ans = max(ans, tmp)

ans = 0
rec(0, len(l)-1)
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = input()
    if len(n) == 1:
        print(n)
        exit()
    else:
        ans = (len(n) - 1) * 9
        t = 0
        for i in range(len(n)):
            t += int(n[i])
        ans = max(ans, t)
        k = int(n)
        for i in range(len(n)-1):
            nn = str(k)
            m = int(nn[len(n) - i - 1:]) + 1
            k -= m
            t = 0
            for j in range(len(str(k))):
                t += int(str(k)[j])
            ans = max(ans, t)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = input()
n = int(N)
t = n % 10 ** (len(N) - 1) + 1
print(max(sum(map(int, N)), sum(map(int, str(n - t)))))

Submission status: Accepted

Solution code:
def main():
    N = list(str(input()))
    if len(N) == 1:
        print(int(N[0]))
    else:
        if all(n == "9" for n in N[1:]):
            print(int(N[0])+9*(len(N)-1))
        else:
            print((int(N[0])-1)+9*(len(N)-1))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=input()
l=len(N)
ten=10**(l-1)
N=int(N)
I=N//ten
after=9*(l-1)
a=str(9)*(l-1)
i=str(I)
v=i+a
V=int(v)
if N>=V:
  print(I+after)
else:
  print(I+after-1)

Submission status: Accepted

Solution code:
N = list(map(int, list(input())))

n = len(N)
if n == 1:
    ans = N[0]
else:
    ans = sum(N) if min(N[1:]) == 9 else N[0] - 1 + 9 * (n - 1)
print(ans)

Submission status: Accepted

Solution code:
n_str = input()
n_int = int(n_str)
n_list = list(map(int,list(n_str)))

def get_max_num():
    digits = len(n_list)
    if digits == 1:
        return n_list[0]
    else:
        # 1桁下げて全ての桁9にする場合を考える
        max_cnt = 0
        for i in range(digits-1):
            max_cnt += 10**i*9
        # 1桁下げて全て9にしたものに、頭に1~9をつけていきNを超えたらbreak
        for i in range(1,10):
            cnt = max_cnt + 10**(digits-1)
            if cnt <= n_int:
                max_cnt = cnt
            else:
                return max_cnt
        #nが全桁9の時、上だと何も返さないので、もう一度returnしてあげる
        return max_cnt

max_num = get_max_num()
max_num_list = list(map(int,list(str(max_num))))
print(sum(max_num_list))

Submission status: Accepted

Solution code:
n = input()
k = len(n)
c = n[0]
if n == c + '9' * (k - 1):
    print(int(n[0]) + 9 * (k - 1))
else:
    print(int(n[0]) + 9 * (k - 1) - 1)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = list(map(int, input()))
    l = len(n)
    dp = [[-float("inf")]*2 for i in range(l+1)]
    dp[0][0] = 0
    for i in range(l):
        ni = i+1
        for j in range(2):
            x = 9 if j else n[i]
            for d in range(x+1):
                nj = j|(d<n[i])
                c = dp[i][j]+d
                if dp[ni][nj] < c:
                    dp[ni][nj] = c
    print(max(dp[l]))
    return
#B
def B():

    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    A()

Submission status: Accepted

Solution code:
number = input()
length = len(number)
t = True
ans = 0
for i in range(length):
    if i > 0 and number[i] != '9':
        t = False
    if i == 0:
        ans += int(number[i])
    else:
        ans += 9

if t:
    print(ans)
else:
    print(ans-1)

Submission status: Accepted

Solution code:
def main():
    N = input()
    m = len(N)
    max_v = sum([int(c) for c in N])
    if m > 1:
        v = int(N[0])-1 + 9*(m-1)
        max_v = max(max_v, v)
    return max_v



if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
N = int(input())
in0 = int(str(N)[0])
Nl = len(str(N))
if (N + 1) % 10 ** (Nl-1) == 0:
    print(9 * (Nl - 1) + in0)
else:
    print(in0 - 1 + (Nl - 1) * 9)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n=S()

  f=False
  for i in range(1,len(n)):
    if n[i]!='9':
      f=True

  if f:
    return int(n[0])-1+9*(len(n)-1)
  else:
    return int(n[0])+9*(len(n)-1)

print(main())

Submission status: Accepted

Solution code:
n=list(map(int,list(input())))
k=len(n)
c=n[0]
f=1
for i in range(1,k):
    if n[i]!=9:
        f=0
if f:
    print(sum(n))
else:
    print(c+9*(k-1)-1)

Submission status: Accepted

Solution code:
N = input()
l = len(N)
k = int(N[0])
Ni = int(N)
if (Ni+1)%(10**(l-1)) == 0:
  print(9*(l-1) + k)
else:
  print(9*(l-1) + k - 1)

Submission status: Accepted

Solution code:
N = input()

ans = 0
for n in N:
    ans += int(n)

for i in range(len(N)):
    tmp = 0
    for j in range(i):
        tmp += int(N[j])

    tmp += int(N[i])-1

    if i < len(N):
        for _ in range(i+1, len(N)):
            tmp += 9

    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools, collections, copy, heapq


def solve(N: int):
    N = list(str(N))
    if all([s == '9' for s in N[1:]]):
        print(int(N[0]) + 9 * (len(N) - 1))
    else:
        print(int(N[0]) - 1 + 9 * (len(N) - 1))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AGC21 A

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = input()
m = len(n)
if m == 1:
    print(int(n))
else:
    flg = False
    for i in range(1,m):
        if int(n[i]) != 9:
            flg = True
            break
    if flg:
        ans = int(n[0])-1
        ans += 9*(m-1)
        print(ans)
    else:
        print(sum(list(map(int,list(n)))))

Submission status: Accepted

Solution code:
N = int(input())
n = len(str(N))
 
ans = 9 * (n - 1)
 
ans += (int(str(N)[0]) - 1)
 
tmp = 0
for i in range(n):
    tmp += int(str(N)[i])
    
print (max(ans, tmp))

Submission status: Accepted

Solution code:
N = int(input())
n = len(str(N))

ans = 9 * (n - 1)

ans += (int(str(N)[0]) - 1)

tmp = 0
for i in range(n):
    tmp += int(str(N)[i])
print (max(ans, tmp))

Submission status: Accepted

Solution code:
ns = list(map(int, list(input())))
print(max(sum(ns), ns[0]-1 + 9*(len(ns)-1)))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

s = input().strip()

c = s[0]
d = len(s)
if s[1:] == "9"*(d-1):
    print(int(c)+9*(d-1))
else:
    print(int(c)-1+9*(d-1))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

n = int(input())

d = 0
tmp = n
while tmp > 0:
    tmp //= 10
    d += 1

if d <= 1:
    print(n)
else:
    if str(n).count("9") == d:
        print(9*d)
    elif str(n)[0] != "9" and str(n)[1:].count("9") == d-1:
        print(int(str(n)[0])+9*(d-1))
    else:
        print(9*(d-1) + n//(10**(d-1)) -1)

Submission status: Accepted

Solution code:
S = input()

ans = sum(map(int, list(S)))
for i in range(len(S)):
    if S[i] == "0":
        continue
    first_half = sum(map(int, list(S[0:i])))
    middle = (int(S[i]) - 1)
    last_half = 9 * (len(S) - i - 1)
    ans = max(ans, first_half + middle + last_half)
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
n = len(str(N))
nine = int("9" * n)

def f(n):
  return sum(map(int, str(n)))

if nine == N:
  print(f(N))
elif N < nine:
  l = str(N)
  x = l[0] + "9"*(len(l)-1)
  if l == x:
    print(f(x))
  else:
    print(f((int(l[0] + "0"*(len(l)-1)))-1))
elif N > nine:
  print(f(nine))

Submission status: Accepted

Solution code:
n = int(input())
i = 0
while i < len(str(n))-1:
    x = int(str(n)[len(str(n))-1-i])
    if x == 9 :
        i += 1
    else:
        n = n-(x+1)*10**i
        i += 1
ans = 0
for i in range(len(str(n))):
    ans += int(str(n)[i])
print(ans)

Submission status: Accepted

Solution code:
n=[int(_) for _ in list(input())]
l=len(n)
if l==1:
    print(n[0])
elif n[0]!=9:
    if len(set(n[1:]))==1 and n[1]==9:
        print(n[0]+9*(l-1))
    else:
        print(n[0]-1+9*(l-1))
else:
    if len(set(n))==1:
        print(9*l)
    else:
        print(9*(l-1)+8)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from functools import lru_cache

@lru_cache()
def F(N):
    if N < 10:
        return N
    q,r = divmod(N,10)
    x1 = F(q) + r
    x2 = F(q-1) + 9
    return max(x1,x2)

answer = F(int(input()))
print(answer)

Submission status: Accepted

Solution code:
a=input();print(int(a[0])+9*~-len(a)-(a[1:]!="9"*~-len(a)!=""))

Submission status: Accepted

Solution code:
N = list(map(int, input()))
N.reverse()
l = []

tmp = sum(N)
l.append(tmp)
#print(N)

for i in range(0,len(N)-1):
    if N[i+1] != 0:
        N[i] = 9
        N[i+1] -= 1
    else:
        index_1 = 1000
        for j in range(i+1,len(N)):
            if N[j] != 0:
                index_1 = j
                break
        if index_1 == 1000:
            break
        else:
            N[index_1] -= 1
            for j in range(i,index_1):
                N[j] = 9
        
    #print(N)
    tmp = sum(N)
    l.append(tmp)

    

print(max(l))

Submission status: Accepted

Solution code:
# 2019/08/06

n=list(map(int,list(input())))
ans=sum(n)
if ans!=n[0]+9*(len(n)-1):
    ans=n[0]-1+9*(len(n)-1)

print(ans)

Submission status: Accepted

Solution code:
s = input()

ans = 0
for ch in s:
    ans += ord(ch) - ord('0')

N = int(s)
B = 0
while 10**B <= N:
    B += 1
B -= 1

ans = max(ans, B * 9 + (N // (10 ** B) - 1))
print(ans)