Решение: Максимальная пара с остатками
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на $d = 160$, и по крайней мере одно из чисел пары делится на $p = 7$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \le N \le 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел $N$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз, а при увеличении параметра $d$ в $k$ раз время работы программы не увеличивается. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом $N$ и $d$.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение по шагам
7 шаговОбрабатываем числа слева направо. Для каждого уже обработанного числа достаточно хранить несколько лучших кандидатов: два максимальных числа с различными остатками и два максимальных числа, делящихся на $7$, также с различными остатками. Если два максимальных значения имеют одинаковый остаток, сохраняем только большее из них.
Пусть текущее число равно $x$, а его остаток по модулю $160$ равен $r$. Если $x$ делится на $7$, то второй элемент пары может быть любым ранее обработанным числом с остатком, не равным $r$. Если $x$ не делится на $7$, второй элемент должен делиться на $7$ и иметь остаток, не равный $r$.
$$$x \bmod 7 = 0 \Rightarrow y \bmod 160 \ne r;\quad x \bmod 7 \ne 0 \Rightarrow y \bmod 7 = 0,\ y \bmod 160 \ne r$$$Из двух сохранённых максимумов выбираем первый, если его остаток отличается от $r$, иначе второй. Проверяем полученную сумму и при необходимости обновляем лучшую пару.
После проверки текущего числа обновляем общий набор двух максимумов и, если число делится на $7$, набор двух максимумов среди чисел, делящихся на $7$. В каждой структуре хранится постоянное число элементов, поэтому память не зависит от $N$ и $d$.
Каждое число обрабатывается за постоянное число операций. Поэтому время работы имеет сложность $O(N)$, а дополнительная память — $O(1)$.
Пример программы на Python 3:
```python
import sys
def add_best(best, value, residue):
"""Добавить значение в список двух максимумов
с различными остатками.
"""
for i, item in enumerate(best):
if item[1] == residue:
if value > item[0]:
best[i] = (value, residue)
break
else:
if value > best[0][0]:
best[1] = best[0]
best[0] = (value, residue)
elif value > best[1][0]:
best[1] = (value, residue)
best.sort(reverse=True)
def get_best_different(best, residue):
for value, saved_residue in best:
if value != 0 and saved_residue != residue:
return value
return 0
n = int(sys.stdin.readline())
best_all = [(0, -1), (0, -1)]
best_div7 = [(0, -1), (0, -1)]
answer_sum = -1
answer_pair = (0, 0)
for _ in range(n):
x = int(sys.stdin.readline())
residue = x % 160
if x % 7 == 0:
y = get_best_different(best_all, residue)
else:
y = get_best_different(best_div7, residue)
if y != 0 and x + y > answer_sum:
answer_sum = x + y
answer_pair = (x, y)
add_best(best_all, x, residue)
if x % 7 == 0:
add_best(best_div7, x, residue)
print(answer_pair[0], answer_pair[1])
```
Алгоритм выполняется за $O(N)$ времени и использует $O(1)$ дополнительной памяти. Программа последовательно обрабатывает числа, поддерживая два максимума с различными остатками среди всех чисел и среди чисел, кратных $7$.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Хранение всех чисел последовательности, что нарушает требование по памяти.
Хранение массива размера $d$, из-за чего память зависит от параметра $d$.
Проверка только того, что одно число делится на $7$, без проверки различных остатков по модулю $160$.
Добавление текущего числа в структуру до проверки пары с ним: в этом случае число может быть ошибочно спарено само с собой.
Хранение только одного максимального значения без второго кандидата с другим остатком.