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

Solution (Python):
from fractions import gcd
from math import factorial, ceil, sqrt, atan2, log, pi, e, asin,acos, cos, sin
from itertools import *
from fractions import Fraction
import string
import copy
import random
import bisect
from decimal import *
def id_generator(size=20, chars=string.digits):
    return ''.join(random.choice(chars) for _ in range(size))
 
def mp():
    return map(int,str(raw_input()).split())

n=input()
s=str(n)
ans=''
if s[0]!='9':
	print max(9*(len(s)-1)+(int(s[0])-1),sum(map(int,list(s))))
else:
	if s[1]=='0':
		print 9*(len(s)-1)+8
	else:
		i=0
		while i<len(s) and s[i]=='9':
			i+=1
		if i==len(s):
			print 9*len(s)
		else:
			if s[i]=='0':
				ans= 9*(len(s)-1)+8
			else:
				ans=9*(len(s)-1)+8
			print ans

Solution (Python):
n = int(input())
num = []
k = n
while k != 0 :
    num.append(k%10)
    k = k//10
print(max(sum(num), num[-1]-1+9*(len(num)-1)))

Solution (Python):
def main():
    N = input()

    if int(N) < 10:
        print(N)
        return

    n = list(map(int, N))
    x = sum(n)
    n[0] -= 1
    n[1:] = [9] * (len(n) - 1)
    print(max(sum(n), x))

main()

Solution (Python):
a=input()

m=sum([int(i) for i in list(a)])
for i in range(1,len(a)):
  t=str(int(a[:i])-1)
  h=a[i:]
  m=max(sum([int(i) for i in list(t)])+9*len(h),m)

print(m)

Solution (Python):
def solve():
    I = input()
    N = list(map(int, list(I)))

    res = sum(N)

    for i in range(len(N)):
        tmp = 0
        for j in range(len(N)):
            if j <= i-1:
                tmp += N[j]
            elif j==i:
                tmp += N[j]-1
            else:
                tmp += 9
        res = max(res, tmp)

    print(res)


if __name__ == "__main__":
    solve()

Solution (Python):
N = input()
n = []
for i in N:
    n.append(int(i))
for i in range(len(n)):
    if i == len(n)-1:
        break
    if n[-(i+1)] != 9:
        n[-(i+1)] = 9
        n[-(i+2)] -= 1
print(sum(n))

Solution (Python):
s = input()
s_n = int(s)
dig = len(s)

if dig == 1:
	cnt = 0
	for i in range(len(s)):
		cnt += int(s[i])
	print(cnt)
	exit(0)

flg = 1
for i in range(1,len(s)):
	if s[i] != '9':
		flg = 0
		break

if flg == 1:
	cnt = 0
	for i in range(len(s)):
		cnt += int(s[i])
	print(cnt)
	exit(0)

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

Solution (Python):

def score(s):
    return sum(map(int, s))


def main():
    s = input()
    best = score(s)
    for i in range(1, len(s)):
        ss = int(s) // 10**i * 10**i - 1
        best = max(best, score(str(ss)))
    print(best)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = sum(map(int, list(str(N))))

c = str(N)[0]

if c == 1:
    B = 9 * (len(str(N))-1)
else:
    B = int(c) + 9 * (len(str(N)) - 1) - 1


print(max(A, B))

Solution (Python):
S = input()
L = len(S)
N = int(S)
ans = sum([int(c) for c in S])
for i in range(1,L):
    tmp = sum([int(c) for c in S[:i]]) - 1
    tmp += 9*(L-i)
    ans = max(ans, tmp)
print(ans)

Solution (Python):
n = input()
total = 0
first = 0
for i in range(len(n)):
	first += int(n[i])
if len(n) == 1:
	print(n)
else:
	for i in range(len(n)):
		if i == 0:
			total += int(n[i]) -1
		else:
			total += 9
	if first < total:
		print(total)
	else:
		print(first)

Solution (Python):
N = input()

def total(n):    
    t = 0
    for i in n:
        t += int(i)
    return t

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

Solution (Python):
n = input()
n2 = [int(i) for i in n[::-1]]
ans = [sum(n2)]
for i in range(len(n2)-1):
    n2[i] = 9
    n2[i+1] -= 1
    ans.append(sum(n2))
ans.append(sum(n2))
print(max(ans))

Solution (Python):
def main():
    N = [int(c) for c in input()]
    for i in range(len(N)):
        s = sum(N)
        ns = N[i]-1 + (len(N) - i - 1) * 9
        if s < ns:
            print(ns)
            return
    print(s)

main()

Solution (Python):
N = input()
l = len(N)
if l == 1:
    print(N)
    exit()
ans = 9 * (l - 1)
if N[1:].count('9') == l - 1:
    ans += int(N[0])
else:
    ans += int(N[0]) - 1
print(ans)

Solution (Python):
def sumOfDigits(a):
    sm = 0
    while(a!=0):
        sm = sm + a % 10
        a = a // 10
     
    return sm
     


def findMax(x) :
     
    
    
    
    b = 1
    ans = x
     
    
    
    while (x!=0) :
        
        
        
        cur = (x - 1) * b + (b - 1)
         
        
        
        
        if (sumOfDigits(cur) > sumOfDigits(ans) or
        (sumOfDigits(cur) == sumOfDigits(ans) and
            cur > ans)) :
                ans = cur
 
        
        
        x =x // 10
        b = b * 10
     
     
    return ans

def sum_digits(n):
    s = 0
    while n:
        s += n% 10
        n //= 10
    return s

n = int(input())
maxDigit = findMax(n)
print(sum_digits(maxDigit))

Solution (Python):



def digit_sum(n):
    return sum(int(c) for c in str(n))


def find_max(x):
    a = x
    b = 1
    while x:
        c = (x - 1) * b + (b - 1)
        dsc = digit_sum(c)
        dsa = digit_sum(a)
        if dsc > dsa or dsc == dsa and c > a:
            a = c
        x //= 10
        b *= 10
    return digit_sum(a)


def main():
    print(find_max(int(input())))


if __name__ == '__main__':
    main()

Solution (Python):
def calc(x):
    r = 0
    while x:
        r += x % 10
        x = x // 10
    return r

def solve0(N):
    r = max(calc(i) for i in range(N + 1))
    return r

def solve(N):
    if N < 10:
        return N
    x = N % 10
    if x == 9:
        return solve(N // 10) + x
    else:
        return solve(N // 10 - 1) + 9

N = int(input())

print(solve(N))

Solution (Python):
N=raw_input()
if len(N)<=1:
  print N
elif N[1:]=="9"*(len(N)-1):
  print sum(map(int, N))
else:
  print int(N[0])-1+9*(len(N)-1)

Solution (Python):
n = input()




maxt1=0
for i in range(len(n)):
    maxt1+= int(n[i])


maxt2=(len(n)-1)*9+int(n[0])-1

print(max(maxt1,maxt2))

Solution (Python):
s = map(int, raw_input().strip())
ans = sum(s)
t = 0
for i, x in enumerate(s):
    if x > 0:
        tt = t + x - 1 + 9 * (len(s) - i - 1)
        if ans < tt:
            ans = tt
        t += x
print ans

Solution (Python):
lis = list(map(int, list(input())))

for i in reversed(range(len(lis))):
    if i - 1 == -1:
        break
    if lis[i] < 9:
        lis[i-1] -= 1
        lis[i] = 9

print(sum(lis))

Solution (Python):
N = input()


def digitsum(n):
    s = str(n)
    S = 0
    for i in s:
        S += int(i)
    return S


d = len(str(N)) - 1
k = int(N[0])
print(max([digitsum(N),digitsum((k*10**d)-1)]))

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

Solution (Python):
N = input()
flag = True
for i in range(1, len(N)):
    if N[i] != '9':
        flag = False
        break

if flag:
    print(int(N[0]) + 9 * (len(N) - 1))
else:
    print(int(N[0]) - 1 + 9 * (len(N) - 1))

Solution (Python):
n = input()
ans = sum(list(map(int, list(n))))
for i in range(len(n)):
    cow = sum(list(map(int, str(int(n[:i+1]) - 1) + str((len(n) - i - 1) * "9"))))
    ans = max(cow, ans)
print(ans)

Solution (Python):
N=input()
cnt=0
for i in range(len(N)):
  cnt+=int(N[i])

a=int(N[0])
a+=(len(N)-1)*9-1
a=max(a,cnt)

print(a)

Solution (Python):
import sys

s=list(input())
ret=0
while True:
    tmp=0
    for i in s:
        tmp+=int(i)
    ret=max(ret,tmp)
    for i in reversed(range(len(s))):
        if s[i]!="9":
            if i==0:
                print(ret)
                sys.exit()
            else:
                j=i-1
                while s[j]=="0":
                    j-=1
                s[j]=str(int(s[j])-1)
                j+=1
                while j<len(s):
                    s[j]="9"
                    j+=1
                break
    else:
        print(ret)
        break

Solution (Python):

N = int(input())
if N < 9:
    print(N)
    exit(0)
n = 0
while True:
    nxt = n * 10 + 9
    if nxt > N:
        break
    n = nxt

ans = n
for i in range(1, 10):
    n1 = int(str(i) + str(n))
    if n1 <= N:
        ans = n1
s = 0
while(ans):
    s += ans % 10
    ans = ans // 10
print(s)

Solution (Python):
a = input()

res = 0
tmp = 0

while True:
    res = max(res, sum(map(int, str(a))) + tmp)
    a /= 10
    if a == 0:break
    a-=1
    tmp += 9

print res

Solution (Python):
INF = 999999999999999999L
EPS = 1e-12

def read():
    return raw_input().strip()

def read_ints():
    return map(int,read().split())

def get_digits(N):
    digs = []
    while N > 0:
        digs.append(N%10)
        N /= 10 
    digs.reverse()
    return digs
        
N = int(read())
digits = get_digits(N)
a1 = sum(digits)
digits = [digits[0]-1] + [9]*(len(digits)-1)

a2 = sum(digits)
print max(a1,a2)

Solution (Python):
N = [int(x) for x in input()]
ans = sum(N)
for i in range(len(N)):
    if i == 0:
        N[0] -= 1
    else:
        N[i] = 9
print(max(ans, sum(N)))

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

Solution (Python):
n=int(input())
ret = 0
i = True
while (n>=9):
    ret += 9
    i = i and (n%10==9)
    n //=10
ret += n-1
if i: ret += 1
print(ret)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    s = str(n)
    a = [int(c) for c in s]
    r = sum(a)
    for i in range(len(a)):
        t = sum(a[:i+1]) - 1
        t += (len(a) - i - 1) * 9
        if r < t:
            r = t


    return r


print(main())

Solution (Python):
n = input()
def F(n):
	return sum(map(int, list(str(n))))

t = 1
z = F(n)
while n > 0:
	n -= n % t
	if n == 0:
		break
	z = max(z, F(n))
	z = max(z, F(n - 1))
	t *= 10
print z