Problem:


Score : 1300 points

Problem Statement

We will call a non-negative integer increasing if, for any two adjacent digits in its decimal representation, the digit to the right is greater than or equal to the digit to the left.
For example, 1558, 11, 3 and 0 are all increasing; 10 and 20170312 are not.

Snuke has an integer N. Find the minimum number of increasing integers that can represent N as their sum.

Constraints

1 \leq N \leq 10^{500000}

Input

The input is given from Standard Input in the following format:

N

Output

Print the minimum number of increasing integers that can represent N as their sum.

Sample Input 1

80

Sample Output 1

2

One possible representation is 80 = 77 + 3.

Sample Input 2

123456789

Sample Output 2

1

123456789 in itself is increasing, and thus it can be represented as the sum of one increasing integer.

Sample Input 3

20170312

Sample Output 3

4

Sample Input 4

7204647845201772120166980358816078279571541735614841625060678056933503

Sample Output 4

31



Sample input:
80


Sample output:
2

Submission status: Wrong Answer

Solution code:
S=input()
ans=0
if len(S)<6:
  while True:
    if len(S)==1:
      ans+=1
      break
    if int(S[0])<=int(S[1]):
      S=S[1:]
    else:
      S=S[1:]
      S=str(int(S)+1)
      ans+=1
  print(ans)
  exit()

      
for i in range(len(S)-8):
  if int(S[i])>int(S[i+1]):
    ans+=1
    
S=S[len(S)-8:]
S=str(int(S)+ans)
while True:
  if len(S)==1:
    ans+=1
    break
  if int(S[0])<=int(S[1]):
    S=S[1:]
  else:
    S=S[1:]
    S=str(int(S)+1)
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
S=list(map(int,list(input())))
ans=0
for i in range(len(S)-1):
  if S[i]>S[i+1]:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
S=input()
ans=0
while True:
  if len(S)==1:
    ans+=1
    break
  if int(S[0])<=int(S[1]):
    S=S[1:]
  else:
    S=S[1:]
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
S=input()
ans=0
a=len(S)
for i in range(a-1):
  if int(S[i])>int(S[i+1]):
    S=str(int(S)+1)
    ans+=1
print(ans+1)

Submission status: Wrong Answer

Solution code:
S=input()
ans=0
while True:
  if len(S)==1:
    ans+=1
    break
  if int(S[0])<=int(S[1]):
    S=S[1:]
  else:
    S=S[1:]
    S=str(int(S)+1)
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
print("0")

Submission status: Wrong Answer

Solution code:
def ketaage(a):
    return a % 100//10 + a % 1000//100 + a % 10000//1000 + a % 100000//10000

n = str(input())
ans = 1
for i in range(len(n)-1):
    if int(n[i]) > int(n[i+1]):
        ans += 1

ans += ketaage(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = str(input())
ans = 1
for i in range(len(n)-1):
    if int(n[i]) > int(n[i+1]):
        ans += 1
print(ans*11//10)

Submission status: Wrong Answer

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

N = input()
for ans in range(len(N)):
    for i, (m, n) in enumerate(zip(N, N[1:] + 'a')):
        if m > n:
            break
    else:
        break

    while i > 0 and N[i] == N[i - 1]:
        i -= 1

    N = N[i + 1:]

print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
k0 = 0
k1 = 5000000

while k1 - k0 > 1:
    k = (k0 + k1) // 2
    t = str(9 * N + k)
    s = 0
    for a in t:
        s += int(a)
    if s <= k:
        k1 = k
    else:
        k0 = k
    
ans = (k1 + 8) // 9
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
D = len(str(N))

X = (10 ** D - 1) // 9
cnt = 0
while X > 0:
    cnt += N // X
    N %= X
    X //= 10

ans = (cnt - 1) // 9 + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・1,11,111,...に分解して9個ずつまとめる
・9倍して考える。9N+x の digit sum <= x となる最小のxが知りたい
・xが満たせばx+1も満たすので、二分探索できる
"""

N = int(read())

N *= 9

def digit_sum(N):
    return sum(map(int,str(N)))

def test(N,x):
    return digit_sum(N + x) <= x

left = 0
right = len(str(N)) * 9 + 100
while left + 1 < right:
    x = (left + right) // 2
    if test(N,x):
        right = x
    else:
        left = x

answer = (right + 8) // 9
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def count(n):
	ans = 0
	while n > 0:
		ans = ans + n % 10
		n //= 10
	return ans
		

def check(k):
	return k >= count(9 * n + k)

n = int(input())
l = 0
r = 5555555
while r - l > 1:
	mid = (l + r) // 2
	if check(mid): 
		r = mid
	else:
		l = mid
print ((r + 8) // 9)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lb,ub,t=0,len(str(n)),9*n
while ub-lb>1:
	mid=(lb+ub)//2
	if sum(map(int,str(t+9*mid)))<=9*mid:
		ub=mid
	else:
		lb=mid
print(ub)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lb,ub=0,len(str(n))
while ub-lb>1:
	mid=(lb+ub)//2
	if sum(map(int,str(9*n+9*mid)))<=9*mid:
		ub=mid
	else:
		lb=mid
print(ub)

Submission status: Time Limit Exceeded

Solution code:
def add(data, v):
    ans = v
    data[1] += v

    for pos in range(1, len(data)):
        if data[pos] >= 10:
            dd = data[pos] / 10

            ans += dd
            data[pos + 1] += dd
            ans -= data[pos]
            data[pos] %= 10
            ans += data[pos]
        else:
            break


    return ans


n = 9 * int(input())

sum = 0
data = [0]

while n > 0:
    dd = n % 10
    data.append(dd)
    sum += dd
    n /= 10

for i in range(50):
    data.append(0)


k = 0
aux = 0
while k <= 500000:
    k += 1
    aux += 9
    sum += add(data, 9)
    if sum <= aux:
        print k
        exit()

Submission status: Time Limit Exceeded

Solution code:
def add(data, v):
    ans = v
    data[1] += v

    for pos in range(1, len(data)):
        if data[pos] >= 10:
            dd = data[pos] / 10

            ans += dd
            data[pos + 1] += dd
            ans -= data[pos]
            data[pos] %= 10
            ans += data[pos]
        else:
            break


    return ans


n = 9 * int(input())

sum = 0
data = [0]

while n > 0:
    dd = n % 10
    data.append(dd)
    sum += dd
    n /= 10

for i in range(50):
    data.append(0)


k = 0
aux = 0
while 1:
    k += 1
    aux += 9
    sum += add(data, 9)
    if sum <= aux:
        print k
        exit()

Submission status: Time Limit Exceeded

Solution code:
def add(data, v):
    ans = v
    data[1] += v

    for pos in range(1, len(data)):
        if data[pos] >= 10:
            dd = data[pos] / 10

            ans += dd
            data[pos + 1] += dd
            ans -= data[pos]
            data[pos] %= 10
            ans += data[pos]
        else:
            break


    return ans


n = 9 * int(input())

sum = 0
data = [0]

while n > 0:
    data.append(n % 10)
    sum += n % 10
    n /= 10

for i in range(50):
    data.append(0)


k = 0
while 1:
    k += 1
    sum += add(data, 9)
    if sum <= 9 * k:
        print k
        exit()

Submission status: Time Limit Exceeded

Solution code:
def add(data, v):
    ans = v
    data[1] += v
    data.append(0)



    for pos in range(1, len(data)):
        if data[pos] >= 10:
            ans += data[pos] / 10
            data[pos + 1] += data[pos] / 10
            ans -= data[pos]
            data[pos] %= 10
            ans += data[pos]
        else:
            break


    return ans


n = 9 * int(input())

sum = 0
data = [0]

while n > 0:
    data.append(n % 10)
    sum += n % 10
    n /= 10


k = 0
while 1:
    k += 1
    sum += add(data, 9)
    if sum <= 9 * k:
        print k
        exit()

Submission status: Time Limit Exceeded

Solution code:
sn = raw_input()
n9 = int(sn) * 9

def check(t):
    global n9
    z = n9 + 9 * t
    sum = 0
    zs = str(z)
    for ch in zs:
        sum += ord(ch) - ord('0')
    return sum <= 9 * t

lo, hi, ans = 1, len(sn) - 1, len(sn)
while lo <= hi:
    mid = (lo + hi) / 2
    if check(mid):
        hi = mid - 1
        ans = mid
    else:
        lo = mid + 1

print ans

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

def ok(n,k):
	if k<0:
		return 0
	
	v = str(9*(n+k))
	d = 0
	for c in v:
		d += int(c[0])
	return 9*k>=d

N=input()
K=1<<20
for i in range(19,-1,-1):
	if ok(N,K-(1<<i)):
		K -= 1<<i

print K

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

def ok(n,k):
	if k<0:
		return 0
	
	v = 9*(n+k)
	d = 0
	while v > 0:
		d += v%10
		v /= 10
	return 9*k>=d

N=input()
K=1<<20
for i in range(19,-1,-1):
	if ok(N,K-(1<<i)):
		K -= 1<<i

print K

Submission status: Time Limit Exceeded

Solution code:
def calc(n):
	s = str(n)
	l, i = len(s), 0
	while i < l - 1 and s[i] <= s[i + 1]: i += 1
	if i == l - 1: return n
	while i > 0 and s[i] == s[i - 1]: i -= 1
	return int(s[ : i] + chr(ord(s[i]) - 1) + '9' * (l - i - 1))

if __name__ == "__main__":
	n, ans = int(raw_input()), 0
	while n:
		#print n
		n -= calc(n)
		ans += 1
	print ans

Submission status: Time Limit Exceeded

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

N = input()
for ans in range(len(N)):
    l = 1
    for i, (m, n) in enumerate(zip(N, N[1:] + 'a')):
        if m > n:
            break
        elif m < n:
            l = i + 2
    else:
        break
    N = N[l:]
    for i in range(len(N) - 1, -1, -1):
        if N[i] == '9':
            N = N[:i] + '0' + N[i + 1:]
        else:
            N = N[:i] + str(int(N[i]) + 1) + N[i + 1:]
            break

print(ans + 1)

Submission status: Time Limit Exceeded

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

N = input()
for ans in range(len(N)):
    l = 1
    for i, (m, n) in enumerate(zip(N, N[1:] + 'a')):
        if m > n:
            break
        elif m < n:
            l = i + 2
    else:
        break

    N = str(int(N) - int(N[:l] + '0' * (len(N) - l)) + 1)

print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
n = [0] + [ord(x) - 48 for x in raw_input()]

nn = len(n)


def add1():
	i = nn - 1
	while n[i] == 9:
		n[i] = 0
		i -= 1
	n[i] += 1

ans = 1
i = 1
while i < nn:
	if n[i - 1] > n[i]:
		j = i - 1
		d = n[i - 1]
		while n[j - 1] == d:
			j -= 1
		n[j] = 0
		add1()
		i = j
		ans += 1
	i += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = "0" + raw_input()

ans = 1
while True:
	for i in xrange(1, len(n)):
		if n[i - 1] > n[i]:
			j = i - 1
			while j >= 0 and n[j - 1] == n[i - 1]:
				j -= 1
			n = "0" + str(int(n[j + 1:]) + 1)
			ans += 1
			break
	else:
		break

print(ans)

Submission status: Time Limit Exceeded

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

N = input()
for ans in range(len(N)):
    for i, (m, n) in enumerate(zip(N, N[1:] + 'a')):
        if m > n:
            break
    else:
        break

    while i > 0 and N[i] == N[i - 1]:
        i -= 1

    N = str(int(N) - int(N[:i + 1] + '0' * (len(N) - i - 1)) + 1)

print(ans + 1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・1,11,111,...に分解して9個ずつまとめる
・9倍して考える。9N+x の digit sum <= x となる最小のxが知りたい
・xが満たせばx+1も満たすので、二分探索できる
"""

N = [x - ord('0') for x in map(int,read().rstrip())][::-1]

# とりあえず 9 倍
N = [9 * x for x in N] + [0] * 10
L = len(N)

for i in range(L-1):
    q,r = divmod(N[i],10)
    N[i] = r
    N[i+1] += q

high1 = sum(N[10:])
N[10] += 1
for i in range(10,L-1):
    if N[i] == 10:
        N[i] = 0
        N[i+1] += 1
high2 = sum(N[10:])
low = N[:10]

low = sum(x * 10 ** i for i,x in enumerate(N[:10]))

A = 10 ** 10

def digit_sum(N):
    return sum(map(int,str(N)))

def test(x):
    if low + x >= A:
        return digit_sum(low + x) - 1 + high2 <= x
    return digit_sum(low + x) + high1 <= x

left = 0
right = 10 ** 10
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = (right + 8) // 9
print(answer)

Submission status: Accepted

Solution code:
n=list(input())
n.reverse()
lb,ub=0,len(n)
def check(x):
	g=0
	for i in n:
		x-=(x+g-int(i))%10
		if x<0:
			break
		g=(x+g)//10
	return x>=0
while ub-lb>1:
	mid=(lb+ub)//2
	if check(9*mid):
		ub=mid
	else:
		lb=mid
print(ub)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here
def sum(x):
    if x<10:
        return x
    ans=divmod(x,10)
    return ans[1]+sum(ans[0])
x=input()
y=int(x)
y*=9
z=int(100000)
z*=z
i=y%z
i=z-i
i+=z
minu=z
while minu>=1:
    if i<minu:
        minu=divmod(minu,10)[0]
        continue
    if sum(y+i-minu)<=(i-minu):
        i-=minu
    else:
        minu=divmod(minu,10)[0]
print(divmod((i+8),9)[0])

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here
def sum(x):
    if x<10:
        return x
    return x%10+sum(x // 10)
x=input()
y=int(x)
y*=9
z=int(100000)
z*=z
i=y%z
i=z-i
i+=z
minu=z
while minu>=1:
    if i<minu:
        minu=minu // 10
        continue
    if sum(y+i-minu)<=(i-minu):
        i-=minu
    else:
        minu=minu // 10
print((i+8) // 9)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here
def sum(x):
    if x<10:
        return x
    return x%10+sum(x//10)
x=input()
y=int(x)
y*=9
z=int(100000)
z*=z
i=y%z
i=z-i
i+=z
minu=z
while minu>=1:
    if i<minu:
        minu=minu//10
        continue
    if sum(y+i-minu)<=(i-minu):
        i-=minu
    else:
        minu=minu//10
print((i+8)//9)

Submission status: Runtime Error

Solution code:
def count(n):
	if n < 10:
		return n
	else:
		return count(n // 10) + n % 10

def check(k):
	return k >= count(9 * n + k)

n = int(input())
l = 0
r = 555555
while r - l > 1:
	mid = (l + r) // 2
	if check(mid): 
		r = mid
	else:
		l = mid
print ((r + 8) // 9)