Как ускорить код (Python 3.7)?

Question

Серийные номера автомобилей “Жорже” являются идущими подряд элементами числовой последовательности N. Десятичная запись i-го элемента этой последовательности строится конкатенацией всех целых положительных чисел, начиная с 1 (номер первого автомобиля) и заканчивая i. Например, N[2]=12, N[11]=1234567891011. При этом, если серийный номер автомобиля делится на 2^S, то его владельцу дарят бесплатную гарантию на 3 года. Вам задано количество экземпляров N и число S. Вычислите, сколько человек получит гарантию. ВНИМАНИЕ! 1 <= S <= 10^18!

Столкнулся с проблемой превышения лимита времени на одной из задач. Превышение лимита всего на 0.089s. Ниже приведен код. Как можно "бустануть его" еще больше, не изменяя сути? Если кто-то знает C++ - перепишите код на него (я учил плюсы год назад). Код (правка 16.05 23:19 - этот код осталось доработать совсем чуть-чуть, он близок к истине):

def go(args):
    N = int(args.split()[0])
    S = int(args.split()[1])
    counter = 0
    S = (1 << S) - 1
    cur = 0
    mul = 10
    minn = min(100001, N + 1)
    for i in range(1, minn):
        if i == mul:
            mul *= 10
        cur = (cur * mul + i) & S
        if not cur:
            counter += 1
    if N > 100000:
        counter *= (N // 100000)
    cur = 0
    mul = 10
    if N > 100000:
        for i in range(0, (N % 100000) + 1):
            if i == mul:
                mul *= 10
            cur = (cur * mul + i) & S
            if not cur:
                counter += 1
    return counter


print(go(input()))

З.З.Ы. Самый быстрый код на данный момент:

def go(args):
    N = int(args.split()[0])
    S = int(args.split()[1])
    counter = 0
    S = (1<<S)-1
    cur = 0
    mul=10
    for i in range(1, N + 1):
        if i == mul :
            mul *= 10
        cur = (cur*mul + i) & S
        if not cur:
            counter += 1
    return counter

Answer 1

def go(args):
    N = int(args.split()[0])
    S = int(args.split()[1])
    counter = 0
    S = (1<<S)-1
    cur = 0
    mul=10
    for i in range(1, N + 1):
        if i == mul :
            mul *= 10
        cur = (cur*mul + i) & S
        if not cur:
            counter += 1
    return counter

Answer 2

Без строк, 100000 6 менее секунды, однако и твой вариант работает не более пары секунд

def go(args):
    serie = int(args.split()[0])
    number = int(args.split()[1])
    counter = 0
    queue = []
    getter = [2, 4, 8, 16, 32, 64][number - 1]
    val = 0
    mul = 10
    for i in range(1, serie + 1):
        if i in (10, 100, 1000, 10000, 100000, 1000000):
            mul *= 10
        val = (val * mul + i) % 1000000
        if val % getter == 0:
            counter += 1
    return counter

 >>100000 6
 >>1562

БЛОГ НА HUSL

Как ускорить код (Python 3.7)?

Ответы (2 шт):