Проблема в коде или же в самой среде?

Question

Решаю задачу 27 из ЕГЭ по информатике и не могу понять: почему при решении задачи перебором цикл, доходя до миллиона, топчется на месте и дальше ничего не вычисляет. Понимаю, что можно привести более экономное по затратам решение, но всё-таки в чем проблема?

file = open("27988_B.txt")
n = int(file.readline())

mas = []

for i in range(n):
    mas.append(int(file.readline()))

max_R = 0

for i in range(n):
    for j in range(i+1, n):
        R = mas[i] * mas[j]
        if R % 26 == 0:
            max_R = R
            print(R)
print(max_R)

Answer 1

Проблема в том, что из файла 27988_B.txt на вход программе подаётся 60000 чисел, проход по вложенным циклам 60000*60000 раз делается очень долго (в Google Colab по моим прикидкам ожидалось где-то минут 15 до конца перебора). Но если посмотреть в файл, то можно увидеть, что одни и те же числа там много раз повторяются, что не удивительно - ведь по условиям задачи числа не могут быть больше 1000, т.е. в списке может быть всего 1000 уникальных чисел, а фактически их ещё меньше. Так что можно сильно сократить время проверки, если оставить для перебора только уникальные числа (можно и сразу собирать числа в множество, но я привожу вариант для простого исправления кода):

mas = list(set(mas))
n = len(mas)

Кстати, у вас в коде вообще нет проверки, что полученное число максимальное из возможных, код нужно поправить (а вот на скриншоте такая проверка есть).

Answer 2

Приведённый код квадратичный, и не подходит для решения при указанных ограничениях (100000 элементов).

Линейный код может выглядеть примерно так. Ищутся максимумы среди чисел, кратных 26 (и следующее по рангу), чётных но не кратных 13, кратных 13 нечётных, и всех остальных.

#mas = [52, 12, 39, 55, 23]
#mas = [53, 12, 39, 55, 23]
#mas = [51, 13, 39, 55, 23]
mas = [52, 12, 39, 51, 23, 78]


max26 = 0
max26_2 = 0
max2 = 0
max13 = 0
maxother = 0

for x in mas:
    if x % 26 == 0:
        if x >= max26:
            max26_2 = max26
            max26 = x
    elif x % 2 == 0:
        max2 = max(max2, x)
    elif x % 13 == 0:
        max13 = max(max13, x)
    else:
        maxother = max(maxother, x)

if max26:
    print(max26 * max(max2, max13, maxother, max26_2))
else:
    print(max2 * max13)

БЛОГ НА HUSL

Проблема в коде или же в самой среде?

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