Решение: Максимальная допустимая пара
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах по крайней мере одно из чисел пары делится на $17$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \leq N \leq 10000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10000$.
Напишите эффективную по времени и памяти программу для решения этой задачи. Программа должна работать за время $O(N)$ и использовать объём памяти, не зависящий от $N$ и не превышающий $1$ Кбайт. Перед текстом программы кратко опишите алгоритм решения и укажите использованный язык программирования и его версию.
Решение по шагам
7 шаговРазность двух чисел чётна тогда и только тогда, когда числа имеют одинаковую чётность. Поэтому пары рассматриваются отдельно для чётных и нечётных чисел.
$$a-b \equiv 0 \pmod 2 \Longleftrightarrow a \equiv b \pmod 2$$В допустимой паре хотя бы одно число должно делиться на $17$. Для каждой чётности достаточно хранить два наибольших числа, кратных $17$, и два наибольших числа вообще. Любая максимальная допустимая пара будет состоять либо из двух чисел, кратных $17$, либо из одного числа, кратного $17$, и любого второго числа той же чётности.
При чтении очередного числа обновляем четыре набора кандидатов: два максимальных кратных $17$ для каждой чётности и два максимальных числа для каждой чётности. Все возможные пары между сохранёнными кандидатами проверяются после чтения всей последовательности.
Если подходящей пары нет, выводятся два нуля. Иначе выводятся два элемента найденной пары. Каждая пара кандидатов содержит два различных элемента последовательности, поскольку при обновлении хранятся два значения с возможным повторением одинаковых чисел.
Язык программирования: Python 3.11.
Программа:
n = int(input())
# Два максимальных числа каждой чётности среди всех чисел.
best_all = [[None, None], [None, None]]
# Два максимальных числа каждой чётности, кратных 17.
best_17 = [[None, None], [None, None]]
def add_value(arr, value):
if arr[0] is None or value >= arr[0]:
arr[1] = arr[0]
arr[0] = value
elif arr[1] is None or value > arr[1]:
arr[1] = value
for _ in range(n):
x = int(input())
parity = x % 2
add_value(best_all[parity], x)
if x % 17 == 0:
add_value(best_17[parity], x)
candidates = []
for parity in (0, 1):
# Пара, в которой оба числа кратны 17.
if best_17[parity][0] is not None and best_17[parity][1] is not None:
candidates.append((
best_17[parity][0] + best_17[parity][1],
best_17[parity][0],
best_17[parity][1]
))
# Пара из кратного 17 и другого числа той же чётности.
if best_17[parity][0] is not None and best_all[parity][1] is not None:
candidates.append((
best_17[parity][0] + best_all[parity][1],
best_17[parity][0],
best_all[parity][1]
))
if not candidates:
print(0, 0)
else:
answer = max(candidates)
print(answer[1], answer[2])
Время работы программы — $O(N)$, так как каждое число обрабатывается один раз, а число операций после чтения входных данных постоянно. Память — $O(1)$: хранятся только несколько чисел и не создаётся структура, размер которой зависит от $N$.
Однопроходный алгоритм на Python 3.11: хранить по два максимальных числа каждой чётности среди всех чисел и среди чисел, кратных 17; затем проверить постоянное число пар-кандидатов. Сложность — O(N) по времени и O(1) по памяти.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверять только пары из двух чисел, кратных 17, хотя достаточно, чтобы кратным 17 было хотя бы одно число.
Считать допустимыми пары разной чётности.
Хранить только одно максимальное число каждой группы и потерять возможность составить пару из двух одинаковых значений.
Использовать массив или список размером N, нарушая требование постоянного объёма памяти.
Разрешить использование одного и того же элемента последовательности дважды.