Форум сайта python.su
x = int(input()) digit = 1 ret = x while ret%10==0: #ищем разряд, который можно уменьшить digit += 1 ret //= 10 ret = ret//10 + 1 #увеличиваем следующий за уменьшаемым разряд(с переносом) ret *= 10**digit #возвращаем отрезанные разряды #теперь осталось прибавить то, чего не хватает sum = 0 while x!=0: sum += x%10 x //= 10 x = ret while x!=0: sum -= x%10 x //= 10 #прибавляем "недосдачу" digit = 0 while sum>9: ret += 9*10**digit digit += 1 sum -= 9 ret += sum*10**digit print(ret)
Отредактировано Euler (Окт. 22, 2013 17:26:00)
Офлайн
sergeekПо условиям задачи 1<=N<=10^100000
на каких данных? на первых 100000 все ок
Офлайн
nokadosты хотя бы прочитал сначала как ты это условие в оп-посте записал.
По условиям задачи 1<=N<=10^100000
Офлайн
sergeekВ питоне?
В любом случае там проблема не в алгоритме
Офлайн
Isemда Схема, например, умеет эффективно исполнять лямбда исчисление
В питоне?
Офлайн
Вот, смотрите, что Я запилил. Надо только подумать тут над двумя вещами (те, что закомментированы)
N = input('Number: ') len_N = len(str(N)) def replace_digits(M): # need to replace end 8 with max 9 from left side return M if N % 10 == 0: p = 0 while N % 10 == 0: N = N / 10 p += 1 M = (N - 1) % 10 + (N / 10 + 1) * 10 ** (p + 1) else: M = N + 9 # need check if 0 appears and put 9 there, after replace_digits if len(str(M)) > len_N: M += N / 10 * 10 M = replace_digits(M) print M
Офлайн
Вообщем получается нужно придумать способ, чтобы программа могла обрабатывать числа длиной до 100 000 символов. В системе тестирования, в которой я проверяю, ни одна из предложенных Вами программ не смогла справится с числом, длиной примерно 80 000 символов, у sergeek ошибка выполнения, У Euler и Isem превышено максимальное время работы.
Отредактировано nokados (Окт. 23, 2013 15:02:32)
Офлайн
nokadosДавайте еще раз посмотрим на исходный код:
У Euler и Isem превышено максимальное время работы.
N = 10**100000 s = [0]+list( map(int, str(N))) print('start') ind = len(s) - 1 for adder in (-1, 1): while 2*s[ind] == 9*(adder+1): ind -= 1 s[ind] += adder ind += adder s[ind:] = sorted(s[ind:]) M = ''.join( map(str,s)) print('end')
Офлайн
nokadosТам же всё разжёвано в комментариях, на больших числах строки быстрее будут:
У Euler и Isem превышено максимальное время работы.
import re 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) print(f(str(x)))
То, что находится до print('start'), что называется, это задание исходных данных.Нет, задание исходных данных это одна строчка N=…, дальше уже обработка.
Отредактировано Euler (Окт. 23, 2013 16:04:45)
Офлайн
Операция
n = str(10**100000)
Офлайн