0

Вот условие: Забавная игра Вы с друзьями играете в следующую игру. Друзья пишут на доске подряд N натуральных чисел. Ваша задача — найти как можно больше подряд идущих чисел, которые бы делились на одно и то же число, большее 1. Так как вручную искать ответ сложно, вы решили написать программу, которая сделает работу за вас.

Входные данные

В первой строке входного файла задано число N(1 ≤ N ≤ 100000). Во второй строке записано через пробел N целых чисел A1...AN(1 ≤ Ai ≤ 1000, 1 ≤ i ≤ N). Это те самые числа, которые написали ваши друзья. Они даны в том же порядке, в котором они расположены на доске.

Выходные данные

Ваша программа должна вывести в выходной файл одно целое число — наибольшее количество подряд идущих чисел заданной последовательности, которые бы делились на одно и то же натуральное число, большее 1.

Вот мое решение, однако оно не проходит по времени:

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


input()
a = [int(i) for i in input().split()]
mx = 0
for i in range(len(a)):
    cur_g = a[i]
    p = 0
    if len(a) - i < mx:
        break
    for j in range(i, len(a)):
        p += 1
        cur_g = gcd(cur_g, a[j])
        if cur_g == 1:
            break
        if mx < p:
            mx = p
print(mx)

Также была идея решить с помощью динамического программирования, но там тоже TL

4

2 ответа 2

1
import random, time

def examp1(a):
    """оригинальный"""
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)

    mx = 0
    for i in range(len(a)):
        cur_g = a[i]
        p = 0
        if len(a) - i < mx:
            break
        for j in range(i, len(a)):
            p += 1
            cur_g = gcd(cur_g, a[j])
            if cur_g == 1:
                break
            if mx < p:
                mx = p
    return mx

def examp2(a):
    """оптимизировано"""
    def gcd(a, b):
        return gcd(b, a % b) if b else a

    la = len(a)
    mx = 0
    for i, cur_g in enumerate(a):
        if la - i < mx:
            break
        p = 0
        for j in range(i, la):
            cur_g = gcd(cur_g, a[j])
            if cur_g == 1:
                break
            p += 1
            if mx < p:
                mx = p
    return mx


def time_(fn, a, x=25):
    """замерять время"""
    tt = []
    for _ in range(x):
        t = time.monotonic()
        fn(a)
        t = time.monotonic() - t
        tt.append(t)
    return sum(tt) / x

if __name__ == '__main__':
    N = 100000
    a = [random.randint(1, 1000) for _ in range(N)]
    t1 = time_(examp1, a)
    t2 = time_(examp2, a)
    print(f'examp1={t1:.2} сек, examp2={t2:.2} сек, выигрыш={(t1/t2)-1:.2%}')

out:

examp1=0.46 сек, examp2=0.37 сек, выигрыш=22.97%
1
  • @vadim_vaduxa, Здравствуйте! Ваше решение examp2 тоже не проходит проверку (на 0.1 секунды). 10 июн 2020 в 17:22
0

Как минимум

inpt=input()
a = [int(i) for i in inpt().split()]

Кроме того, не вычичслять постоянно len(a), а сделать вначале один раз,

len_a=len(a)

а затем использовать эту переменную.

Кроме того, вызов рекурсивной реализации функции gcd внутри циклв тоже может существенно ухудшить время выполнения.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.