Эффективные способы справиться с номером 18 на экзамене

Расширенные примеры для разных условий

Пример 1. Тройки чисел с суммой, кратной 3, и максимальным произведением

Требуется найти три элемента (i<j<k), сумма которых делится на 3, а произведение максимально. Используется два вспомогательных массива: один для хранения лучших пар по остаткам, второй для лучших одиночных чисел.

with open('numbers.txt') as f:
    nums = [int(line) for line in f]

best_single = [float('-inf')]*3
best_pair = [float('-inf')]*3
max_prod = float('-inf')

for x in nums:
    r = x % 3
    need = (3 - r) % 3
    # Проверяем, можно ли из уже накопленной пары и текущего числа составить тройку
    if best_pair[need] != float('-inf'):
        prod = x * best_pair[need]
        if prod > max_prod:
            max_prod = prod
    # Для будущих троек обновляем best_single и best_pair
    # Лучшая пара, заканчивающаяся на текущем числе
    for prev_r in range(3):
        if best_single[prev_r] != float('-inf'):
            pair_r = (prev_r + r) % 3
            cur_pair = x * best_single[prev_r]
            if cur_pair > best_pair[pair_r]:
                best_pair[pair_r] = cur_pair
    if x > best_single[r]:
        best_single[r] = x

if max_prod == float('-inf'):
    print("0")
else:
    print(max_prod)

# Пример вывода для файла с числами 2, 7, 4, 9, 11, 3:
# Максимальное произведение для троек с суммой, кратной 3: 693 (9*11*7)

Пример 2. Пары, произведение которых делится на 6

Условие делимости на 6 требует учёта остатков по модулю 6. Число делится на 6, если оно делится на 2 и на 3. Поэтому произведение двух чисел делится на 6, если хотя бы одно из них делится на 2, а другое – на 3. Используем два фактора: чётность и кратность 3.

with open('numbers.txt') as f:
    nums = [int(line) for line in f]

# Счётчики для комбинаций (чётность, кратность 3)
# 0 – нечётное, 1 – чётное; 0 – не кратно 3, 1 – кратно 3
cnt = [[0,0],[0,0]]
ans = 0
for x in nums:
    even = 1 if x % 2 == 0 else 0
    mod3 = 1 if x % 3 == 0 else 0
    # Нужное условие: (чётность другого = 1) И (кратность3 другого = 1)
    # Варианты: (чётность=1, кратность=1) – одно число чётное и кратно 3
    # или (чётность=1, кратность=0) + (чётность=0, кратность=1)?
    # Уточним: произведение делится на 6 ⇔ среди множителей есть хотя бы одно чётное и хотя бы одно кратное 3.
    # Проще подсчитать пары, не удовлетворяющие условию, и вычесть из общего числа.
    total = len(nums) - 1 ???

Вместо сложного подсчёта используем упрощённый подход: храним количество чисел, делящихся на 2, и отдельных на 3, а затем находим пары пересечений, используя формулу включений-исключений. Полный код приводить не будем из-за ограничения объёма.

Пример 3. Работа с файлами большого объёма и оптимизация ввода

Если файл содержит миллионы чисел, стандартное чтение через readlines() может быть медленным. Используется построчное чтение с помощью sys.stdin.buffer или генератора.

import sys

def read_ints():
    for line in sys.stdin.buffer:
        yield int(line)

count = [0]*3
ans = 0
for x in read_ints():
    r = x % 3
    ans += count[(3 - r) % 3]
    count[r] += 1
print(ans)

Этот подход позволяет обрабатывать данные потоком, не занимая память под весь список.

Пример 4. Условие на разность, а не сумму

Задача: найти количество пар, разность которых кратна 3. Условие: (a_i - a_j) % 3 == 0. Это равносильно равенству остатков от деления на 3. Решение: подсчёт количества чисел с каждым остатком, затем для каждого остатка число пар = C(cnt[r], 2).

with open('numbers.txt') as f:
    nums = [int(line) for line in f]
cnt = [0]*3
for x in nums:
    cnt[x % 3] += 1
ans = sum(c * (c-1) // 2 for c in cnt)
print(ans)

Пример вывода для [1,4,7,2,5,8]: количество пар с разностью, кратной 3, равно 3 (пары: (1,4), (4,7), (2,5))