Numerot

#!/usr/bin/python3
 
def f(luku, maxnum = 0, cache = dict()):
	key = (maxnum, luku)
	if key in cache:
		return cache[key]
	if luku < maxnum:
		return 1, -maxnum
	if luku <= 9:
		if maxnum == 0:
			return 1, -luku
		return 2, -(luku + maxnum)
 
	askelia = 0
	muutos = 0
	while luku > 9:
		s = str(luku)[::-1]
		muutettu = False
		for i in range(1, len(s) - 1):
			if s[i] != "0":
				newmaxnum = max(maxnum, max(int(s[j]) for j in range(i+1, len(s))))
				a, m = f(luku % (10**(i+1)), newmaxnum)
				askelia += a
				muutos += m
				luku += m
				muutettu = True
				break
		if not muutettu:
			askelia += 1
			num = max(maxnum, int(s[-1]), int(s[0]))
			muutos -= num
			luku -= num
	cache[key] = askelia, muutos
	return cache[key]
 
def helppo(alkumax, ylin, nollia, alin, cache = dict()):
	key = (alkumax, ylin, nollia, alin)
	if key in cache:
		return cache[key]
 
	askelia, muutos = 0, 0
	while ylin > 0:
		# Nyt luku on muotoa {ylin}00000{alin}
		# Aiheutetaan kymmenylitys, jossa ylin laskee yhdellä.
		maxnum = max(alkumax, ylin, alin)
		if maxnum <= alin:
			maxnum2 = max(alkumax, ylin, alin - maxnum)
			askelia += 2
			muutos -= maxnum + maxnum2
			alin = (alin - maxnum - maxnum2) % 10
		else:
			askelia += 1
			muutos -= maxnum
			alin = (alin - maxnum) % 10
		ylin -= 1
 
		if nollia > 0:
			# Nyt luku on muotoa {ylin}99999{alin}
			# Tuhotaan yhdeksiköt pienimmästä alkaen.
			for i in range(nollia - 1):
				maxnum = 9
				a, m = helppo(9, 9, i, alin)
				askelia += a
				muutos += m
				alin = (alin + m) % 10
 
			# Nyt luku on muotoa {ylin}90000{alin}
			i = nollia - 1
			maxnum = max(alkumax, ylin)
			a, m = helppo(maxnum, 9, i, alin)
			askelia += a
			muutos += m
			alin = (alin + m) % 10
 
	val = (askelia, muutos)
	cache[key] = val
	return val
 
def f(luku, maxnum = 0, cache = dict()):
	askelia, muutos = 0, 0
	kymppi = 10
	nollia = 0
	while luku > 9:
		ylin = luku // kymppi % 10
		alin = luku % 10
		alkumax = max(int(i) for i in str(luku // kymppi // 10))
		a, m = helppo(max(maxnum, alkumax), ylin, nollia, alin)
		askelia += a
		muutos += m
		luku += m
		kymppi *= 10
		nollia += 1
	return askelia, muutos
 
#print((10812292252, -91723876114), "oikea")
#print(f(91723876123, 0), "laskettu")
 
#print((1092, -9828), "oikea")
#print(f(9829, 9), "laskettu")
 
def g(x):
	return f(x)[0] + 1
 
t = int(input())
for _ in range(t):
	x = int(input())
	if x == 1:
		print(1)
		continue
	k0, k1 = 9, 10**19
	while (k1 - k0) > 1:
		k = (k1 + k0) // 2
		if g(k) < x:
			k0 = k
		else:
			k1 = k
	print(k1)

Test 1

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED