Задание 17 ЕГЭ: пары любых элементов

Пары любых элементов. Тема номера — обработка последовательности из файла. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Задание выполняется с использованием прилагаемого файла.

В файле 17.txt содержится последовательность из 5000 натуральных чисел. Элементы последовательности могут принимать целые значения от 1 до 100 000 включительно. Определите количество пар элементов последовательности, у которых сумма элементов кратна 146, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два различных элемента последовательности (порядок элементов в паре не важен).

Запишите два числа через пробел.

Скачать файл к примеру

Решение

Всего пар 12 497 500: двойной цикл по всем парам работал бы слишком долго. Сумма кратна 146, когда остатки от деления на 146 в сумме дают 0 или 146. Для очередного x все его партнёры уже прочитаны: храним, сколько было чисел с каждым остатком и наибольшее из них. Само x добавляем в таблицы только после подсчёта, иначе оно составит пару само с собой.

Ответ: 85961 199582.

a = [int(s) for s in open("17.txt")]

m = 146
cnt = [0] * m      # сколько уже прочитано чисел с каждым остатком
mx = [0] * m       # наибольшее из них
count = best = 0
for x in a:
    need = (m - x % m) % m      # остаток партнёра
    if cnt[need]:
        count += cnt[need]
        best = max(best, x + mx[need])
    r = x % m
    cnt[r] += 1
    mx[r] = max(mx[r], x)
print(count, best)

Решить такую задачу — новый вариант с проверкой