DjangoBB LoFi version

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

1 2 3

nokados

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

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

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

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

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

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

noob_saibot

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

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

sergeek

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

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

noob_saibot

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

sergeek

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

nokados

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

sergeek

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

Isem

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

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 )

sergeek

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

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)

Master_Sergius

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

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

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

FishHook

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

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

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

Master_Sergius

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

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