Isem
Операция

n = str(10**100000)

уже работает более 0.5 сек на 3ГГц процессоре.

import re
import time
x = 10**100000
def f(x):
	m = re.match("^(\d*?)(\d0*)$", '0'+x)
	part1 = str(int(m.group(1))+1)
	delta = (sum(map(int, x))-sum(map(int, part1)))
	part2 = str(delta%9)+'9'*(delta//9)
	return int(part1)*10**len(m.group(2))+int(part2)
start = time.time()
f(str(x))
print (time.time() - start)

Isem
А как насчет x = 10**100000-1 или x = 10**100000 - 10**10000 + 1 ?
А еще лучше, когда x = 10**100000 - 10**99999 + 1.

Euler
Сказал же уже

Euler
избавься от регулярки и мапов

Euler
Вообще задача не для питона - питон простой, удобный, но никак не быстрый.

Isem
Твой код - вот ты и избавляйся.

Euler
Я у себя проверил, алгоритм укладывается в отведённое время

Isem
А как насчет x = 10**100000-1 или x = 10**100000 - 10**10000 + 1 ?
А еще лучше, когда x = 10**100000 - 10**99999 + 1.

Euler
Хамство тебе тут никак не поможет.

Isem
Спасибо, мне помощь не нужна.

Isem
Хамите вы, сударь.

Euler
Где именно?