Задание 5. Информатика. ЕГЭ. Поляков-5446

(В. Шубинкин) Автомат получает на вход номер банковской карты (число \(N\) из \(16\) цифр) и строит по нему контрольное число \(S\) следующим образом (вариант алгоритма Лу́на):

1. Цифры числа нумеруются справа налево, начиная с нуля.
2. Цифры, стоящие на нечётных позициях, увеличиваются в два раза. Если при этом получается двузначное число, его цифры складываются.
3. Число \(S\) вычисляется как сумма всех цифр на чётных позициях и преобразованных цифр на нечётных позициях.

Например, для числа \(4096~8308~0309~8323\) сумма цифр на чётных позициях (с конца) \(3+3+9+3+8+3+6+0=35,\) сумма преобразованных цифр на нечётных позициях \(4+7+0+0+0+7+9+8=35.\) Общая сумма \(S = 70.\)

Найдите наименьший номер банковской карты \(N,\) для которого результатом работы алгоритма будет число \(30.\) В ответе укажите остаток от деления найденного числа \(N\) на \(10^8.\)

def conv(x):
    d = 2 * int(x)
    return d % 10 + d // 10


def lun(n):
    ns = str(n)
    even = sum(int(x) for x in ns[1::2])
    odd = sum(conv(x) for x in ns[::2])
    return even + odd

#print(lun(4096830803098323))
for N in range(1, 10**10):
    if lun(N) == 30:
        print(N % 10**8)
        break