DjangoBB LoFi version

Начало » Центр помощи » Задача "Следующее число"

1 2 3

Euler

Окт. 22, 2013 14:43:54

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)

можно менять десятку на любое натуральное основание больше единицы с минимальной модификацией.

nokados

Окт. 22, 2013 17:22:29

sergeek
на каких данных? на первых 100000 все ок

По условиям задачи 1<=N<=10^100000

sergeek

Окт. 22, 2013 18:30:01

nokados
По условиям задачи 1<=N<=10^100000

ты хотя бы прочитал сначала как ты это условие в оп-посте записал.
В любом случае там проблема не в алгоритме.

Isem

Окт. 23, 2013 02:20:33

sergeek
В любом случае там проблема не в алгоритме

В питоне?

sergeek

Окт. 23, 2013 08:40:17

Isem
В питоне?

да

Схема, например, умеет эффективно исполнять лямбда исчисление

Master_Sergius

Окт. 23, 2013 12:53:44

Вот, смотрите, что Я запилил. Надо только подумать тут над двумя вещами (те, что закомментированы)

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

nokados

Окт. 23, 2013 15:00:48

Вообщем получается нужно придумать способ, чтобы программа могла обрабатывать числа длиной до 100 000 символов. В системе тестирования, в которой я проверяю, ни одна из предложенных Вами программ не смогла справится с числом, длиной примерно 80 000 символов, у sergeek ошибка выполнения, У Euler и Isem превышено максимальное время работы.

Isem

Окт. 23, 2013 15:20:12

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')

То, что находится до print('start'), что называется, это задание исходных данных. Надеюсь, они не должны включаться в общее время счета так же, как и вывод данных, который в этом примере отсутствует. Можете сформировать входное число в файле (например, 200 тыс цифр) в список s и затем переменную M записать в другой файл, но не учитывать время этих операций и замерить время работы алгоритма.

Euler

Окт. 23, 2013 16:02:32

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)))

можно ещё в несколько раз ускорить, если отказаться от регулярки и map, но должно и так укладываться с запасом.

То, что находится до print('start'), что называется, это задание исходных данных.

Нет, задание исходных данных это одна строчка N=…, дальше уже обработка.

Isem

Окт. 23, 2013 16:17:13

Операция

n = str(10**100000)

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