Уведомления

Группа в Telegram: @pythonsu

#1 Окт. 21, 2013 15:23:27

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

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

Ограничение времени: 0.5 секунда
Ограничение памяти: 16 Мегабайта
Ввод: стандартный поток ввода (stdin)
Вывод: стандартный поток вывода (stdout)


Для заданного натурального числа N найти минимальное число M,
большее N, с той же, что у N, суммой цифр.

Исходные данные
В единственной строке записано число N (1  N  10100000).

Результат
Вывести единственное число M.

Пример
Исходные данные | Результат
524 | 533
1 | 10
999 | 1899



моя подпись

Офлайн

#2 Окт. 21, 2013 16:55:55

noob_saibot
Зарегистрирован: 2013-09-11
Сообщения: 495
Репутация: +  20  -
Профиль   Отправить e-mail  

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

В режиме Ванги сообщаю:
“Вам будут неохотно помогать без вашего кода. А вот его с радостью подлатают”

Офлайн

#3 Окт. 22, 2013 09:51:09

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

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

from functools import reduce
 
print((lambda n : (lambda R: (lambda ns : (R(lambda self, x, xs, o, ts :
                              x and (lambda nxs : nxs + 
                                     (lambda nn, nh : reduce(lambda res, n : res*10 + n,
                                                             [nh] + [9]*nn,
                                                             0))
                                       (*divmod(ns(xs) - ns(nxs) + ts + x, 9)))
                                      ((xs+1)*o*10) or self(xs, o*10, ts+x)))
                              (n, 1, 0))
                   (R(lambda self, x, xs: xs and x + self(xs) or x)))
       (lambda f : (lambda hR : hR(hR))
                   (lambda r : lambda d, *a : f(r(r), *(tuple(reversed(divmod(d, 10))) + a)))))
      (int(input('your number?? '))))

Офлайн

#4 Окт. 22, 2013 10:43:55

noob_saibot
Зарегистрирован: 2013-09-11
Сообщения: 495
Репутация: +  20  -
Профиль   Отправить e-mail  

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

sergeek
сломал систему…

Офлайн

#5 Окт. 22, 2013 12:13:40

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

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

sergeek
Можешь объяснить, как она работает? И, кстати - работает не всегда верно.



моя подпись

Отредактировано nokados (Окт. 22, 2013 12:13:54)

Офлайн

#6 Окт. 22, 2013 12:48:01

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

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

N = 1239560
s = [0]+list( map(int, str(N)))
ind = len(s) - 1
for adder in (-1, 1):
    while 2*s[ind] == 9*(adder+1): ind -= 1
    s[ind] += adder
    ind += adder
    
s = s[:ind] + sorted(s[ind:])
M = int(''.join( map(str,s)))
print( N, '->', M )



Офлайн

#7 Окт. 22, 2013 13:22:16

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

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

nokados
Можешь объяснить, как она работает?
нет ( в смысле мне действительно сложно это сделать)
nokados
И, кстати - работает не всегда верно
на каких данных? на первых 100000 все ок
from functools import reduce
R = lambda f : (lambda hR : hR(hR))(lambda r : lambda d, *a : f(r(r), *(tuple(reversed(divmod(d, 10))) + a)))
ns = R(lambda self, x, xs: xs and x + self(xs) or x)
fast_next = lambda n : (R(lambda self, x, xs, o, ts :
                          x and (lambda nxs : nxs + (lambda nn, nh : reduce(lambda res, n : res*10 + n,
                                                                     [nh] + [9]*nn,
                                                                     0))
                          (*divmod(ns(xs) - ns(nxs) + ts + x, 9)))
                         ((xs+1)*o*10) or  self(xs, o*10, ts+x)))(n, 1, 0)
 
def slow_next(n):
    ns = lambda n : sum(map(int, str(n)))
    nsum = ns(n)
    n+=1
    while ns(n) != nsum:
        n+=1
    return n
 
def isem_next(N):
    s = [0]+list( map(int, str(N)))
    ind = len(s) - 1
    for adder in (-1, 1):
        while 2*s[ind] == 9*(adder+1): ind -= 1
        s[ind] += adder
        ind += adder
    s = s[:ind] + sorted(s[ind:])
    M = int(''.join( map(str,s)))
    return M
 
for n in range(1,100000):
    by_slow, by_fast, by_isem = slow_next(n), fast_next(n), isem_next(n)
    assert by_slow == by_fast == by_isem, 'FAIL at {}: {},{},{} '.format(n, by_slow, by_fast, by_isem)

Офлайн

#8 Окт. 22, 2013 14:11:13

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

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

Фокус тут в математике. Если в записи числа нет цифры 9, то решение вот:
N = input('Number: ')
print N + 9

Если же цифры 9 есть, то надо ещё подумать. Но тут тоже не должны быть сложные циклы, а спец формулы



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

Офлайн

#9 Окт. 22, 2013 14:14:16

FishHook
От:
Зарегистрирован: 2011-01-08
Сообщения: 8312
Репутация: +  568  -
Профиль   Отправить e-mail  

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

Master_Sergius
Фокус тут в математике. Если в записи числа нет цифры 9, то решение вот:
N = input('Number: ')
print N + 9

120 -> (1+2 =3)
120 +9 -> (1+2+9=12)



Офлайн

#10 Окт. 22, 2013 14:18:00

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

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

Ага, значит, ещё и на 0 надо обращать внимание )
Но тут полюбасу есть математический трюк…



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

Офлайн

Board footer

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

Powered by DjangoBB

Lo-Fi Version