Решение: Максимальная пара с делителем 19
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах хотя бы одно из чисел делится на 19. Порядок элементов в паре неважен. Среди всех таких пар требуется найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар нет, необходимо вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \leq N \leq 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения задачи. Эффективная по времени программа должна работать за время, не превышающее линейное относительно $N$. Память, необходимая для хранения всех переменных программы, не должна превышать 1 Кбайт и не должна увеличиваться с ростом $N$.
Перед текстом программы кратко опишите алгоритм решения и укажите использованный язык программирования и его версию.
Решение по шагам
7 шаговРазность двух чисел чётна тогда и только тогда, когда числа имеют одинаковую чётность. Поэтому достаточно рассматривать отдельно пары чётных и пары нечётных чисел.
При обработке очередного числа $x$ возможная подходящая пара должна содержать либо само число $x$, если оно делится на 19, либо ранее встреченное число той же чётности, делящееся на 19.
Чтобы получить максимальную сумму с текущим числом, достаточно хранить для каждой чётности максимальное число вообще и максимальное число, кратное 19. Все эти значения можно обновлять после проверки пар с текущим числом.
Если $x$ кратно 19, его можно объединить с максимальным ранее встреченным числом той же чётности. Если среди ранее обработанных чисел той же чётности есть число, кратное 19, его можно объединить с $x$ независимо от делимости $x$ на 19.
Каждое число обрабатывается один раз, выполняется постоянное число сравнений и обновлений. Время работы программы составляет $O(N)$, а используется только постоянное количество переменных, то есть память составляет $O(1)$.
Программа на Python 3:
```python
best = [-1, -1]
best19 = [-1, -1]
ans_sum = -1
ans_pair = (0, 0)
n = int(input())
for _ in range(n):
x = int(input())
parity = x % 2
if x % 19 == 0 and best[parity] != -1:
if x + best[parity] > ans_sum:
ans_sum = x + best[parity]
ans_pair = (best[parity], x)
if best19[parity] != -1:
if x + best19[parity] > ans_sum:
ans_sum = x + best19[parity]
ans_pair = (best19[parity], x)
if x > best[parity]:
best[parity] = x
if x % 19 == 0 and x > best19[parity]:
best19[parity] = x
if ans_sum == -1:
print(0, 0)
else:
print(ans_pair[0], ans_pair[1])
```
Алгоритм использует четыре максимальных значения: максимальное число каждой чётности и максимальное число каждой чётности, кратное 19. Все числа обрабатываются за один проход; время работы $O(N)$, дополнительная память $O(1)$. Программа приведена на Python 3.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверять только пары, в которых первое число кратно 19, и пропускать случай, когда кратно 19 второе число.
Считать подходящими числа разной чётности.
Обновлять максимальные значения до проверки пары с текущим числом и тем самым использовать один и тот же элемент дважды.
Хранить всю последовательность, нарушая требование по памяти.
Выводить нули, если подходящей пары нет, но не обрабатывать случай отсутствия значения, кратного 19, для нужной чётности.