Ответ: Максимальная сумма пары
Алгоритм работает за $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)
У этого задания официального ключа нет, поэтому ответ получен в разборе и с ключом не сверен. Перед тем как заучивать результат, пройдите выкладки — там видно, откуда взялось каждое число.
В бланк: число или слово без единиц измерения; дробную часть отделяйте запятой.
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на $d = 120$, и по крайней мере одно из чисел пары делится на $p = 7$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \leq N \leq 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения этой задачи. Опишите алгоритм решения перед текстом программы и укажите использованный язык программирования и его версию. Программа должна использовать не более 1 Кбайт памяти, а её время работы не должно зависеть от параметра $d$.
Где здесь ошибаются
Разрешают пару двух чисел с одинаковыми остатками по модулю 120.
Проверяют делимость на 7 только для текущего числа, но не учитывают делимость ранее сохранённого числа.
Обновляют максимумы до проверки пары с текущим числом и тем самым используют один и тот же элемент дважды.
Хранят все входные числа или матрицу пар, из-за чего нарушается ограничение по памяти.
Выводят два нуля при отсутствии пары, но не обрабатывают случай, когда подходящая пара не найдена.