Решение: Максимальная сумма пары
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на $d = 120$, и по крайней мере одно из чисел пары делится на $p = 7$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \leq N \leq 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения этой задачи. Опишите алгоритм решения перед текстом программы и укажите использованный язык программирования и его версию. Программа должна использовать не более 1 Кбайт памяти, а её время работы не должно зависеть от параметра $d$.
Решение по шагам
5 шаговЧисла рассматриваются по одному. Для каждого остатка от деления на $120$ храним два максимальных значения: максимальное число, делящееся на $7$, и максимальное число, не делящееся на $7$. Вместе с каждым значением сохраняем само число.
Для очередного числа $x$ перебираем все остатки $r$, отличные от $x \bmod 120$. Пара допустима, если $x$ делится на $7$ или сохранённое число делится на $7$. Поэтому при $x$, кратном $7$, можно брать максимальное сохранённое число любого типа, а иначе — только максимальное число, кратное $7$.
Если найденная сумма больше текущей максимальной суммы, запоминаем пару. После проверки помещаем $x$ в соответствующую группу остатка и при необходимости заменяем хранимый максимум.
$$O(N \cdot d)$$В данной задаче $d=120$, поэтому перебор 120 остатков является константным относительно $N$. Используется постоянное количество переменных и массивов фиксированного размера, то есть память не растёт с $N$ и $d$.
$$O(N)$$Один из вариантов программы на Python 3:
Алгоритм работает за $O(N \cdot 120)=O(N)$ по времени и использует $O(120)=O(1)$ памяти. Программа на Python 3:
best_div = [-1] * 120
best_not_div = [-1] * 120
answer_a = 0
answer_b = 0
best_sum = -1
n = int(input())
for _ in range(n):
x = int(input())
rem = x % 120
x_div = (x % 7 == 0)
for old_rem in range(120):
if old_rem == rem:
continue
if x_div:
candidate = best_div[old_rem]
if candidate == -1 or best_not_div[old_rem] > candidate:
candidate = best_not_div[old_rem]
else:
candidate = best_div[old_rem]
if candidate != -1 and x + candidate > best_sum:
best_sum = x + candidate
answer_a = x
answer_b = candidate
if x_div:
if x > best_div[rem]:
best_div[rem] = x
else:
if x > best_not_div[rem]:
best_not_div[rem] = x
if best_sum == -1:
print(0, 0)
else:
print(answer_a, answer_b)
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Разрешают пару двух чисел с одинаковыми остатками по модулю 120.
Проверяют делимость на 7 только для текущего числа, но не учитывают делимость ранее сохранённого числа.
Обновляют максимумы до проверки пары с текущим числом и тем самым используют один и тот же элемент дважды.
Хранят все входные числа или матрицу пар, из-за чего нарушается ограничение по памяти.
Выводят два нуля при отсутствии пары, но не обрабатывают случай, когда подходящая пара не найдена.