Уведомления

Группа в Telegram: @pythonsu

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

Euler
Зарегистрирован: 2013-07-30
Сообщения: 43
Репутация: +  1  -
Профиль   Отправить e-mail  

Задача "Следующее число"

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)

Офлайн

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

nokados
От: Ростов
Зарегистрирован: 2013-10-15
Сообщения: 52
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача "Следующее число"

sergeek
на каких данных? на первых 100000 все ок
По условиям задачи 1<=N<=10^100000



моя подпись

Офлайн

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

sergeek
Зарегистрирован: 2012-06-26
Сообщения: 470
Репутация: +  43  -
Профиль   Отправить e-mail  

Задача "Следующее число"

nokados
По условиям задачи 1<=N<=10^100000
ты хотя бы прочитал сначала как ты это условие в оп-посте записал.
В любом случае там проблема не в алгоритме.

Офлайн

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

Isem
От:
Зарегистрирован: 2010-08-27
Сообщения: 447
Репутация: +  7  -
Профиль   Отправить e-mail  

Задача "Следующее число"

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



Офлайн

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

sergeek
Зарегистрирован: 2012-06-26
Сообщения: 470
Репутация: +  43  -
Профиль   Отправить e-mail  

Задача "Следующее число"

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

Офлайн

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

Master_Sergius
Зарегистрирован: 2013-09-12
Сообщения: 271
Репутация: +  7  -
Профиль   Отправить e-mail  

Задача "Следующее число"

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

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 



———————————————————————————
Мой блог о семействе *nix: http://nixtravelling.blogspot.com/

Офлайн

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

nokados
От: Ростов
Зарегистрирован: 2013-10-15
Сообщения: 52
Репутация: +  0  -
Профиль   Отправить e-mail  

Задача "Следующее число"

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



моя подпись

Отредактировано nokados (Окт. 23, 2013 15:02:32)

Офлайн

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

Isem
От:
Зарегистрирован: 2010-08-27
Сообщения: 447
Репутация: +  7  -
Профиль   Отправить e-mail  

Задача "Следующее число"

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 записать в другой файл, но не учитывать время этих операций и замерить время работы алгоритма.



Офлайн

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

Euler
Зарегистрирован: 2013-07-30
Сообщения: 43
Репутация: +  1  -
Профиль   Отправить e-mail  

Задача "Следующее число"

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=…, дальше уже обработка.

Отредактировано Euler (Окт. 23, 2013 16:04:45)

Офлайн

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

Isem
От:
Зарегистрирован: 2010-08-27
Сообщения: 447
Репутация: +  7  -
Профиль   Отправить e-mail  

Задача "Следующее число"

Операция

n = str(10**100000)
уже работает более 0.5 сек на 3ГГц процессоре.



Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version