Задание 27 ЕГЭ по информатике · 2931D9

1. Разность элементов пары должна быть чётной, поэтому оба элемента должны иметь одинаковую чётность. Обрабатываем отдельно чётные и нечётные числа.
a mod 2=b mod 2

2. Для каждой чётности сохраняем два наибольших числа среди всех чисел и два наибольших числа, кратных 21. Два элемента нужны потому, что элементы пары должны быть различными элементами последовательности, даже если их значения совпадают.

3. Любая оптимальная пара состоит из сохранённых кандидатов: если элемент не входит в два наибольших числа своей чётности или в два наибольших числа, кратных 21, его можно заменить на более крупный допустимый элемент, не уменьшая сумму.

4. Перебираем все пары сохранённых кандидатов одной чётности. Оставляем только пары, в которых хотя бы один элемент делится на 21, и выбираем пару с наибольшей суммой.

5. Алгоритм выполняет постоянное число операций для каждого из N чисел, поэтому работает за O(N) и использует O(1) памяти.

6. Пример программы на Python 3:
from sys import stdin

n = int(stdin.readline())
all_best = [[], []]
div_best = [[], []]

for _ in range(n):
x = int(stdin.readline())
parity = x % 2

all_best[parity].append(x)
all_best[parity].sort(reverse=True)
del all_best[parity][2:]

if x % 21 == 0:
div_best[parity].append(x)
div_best[parity].sort(reverse=True)
del div_best[parity][2:]

answer = None

for parity in (0, 1):
candidates = []
for x in all_best[parity] + div_best[parity]:
if x not in candidates:
candidates.append(x)

for i in range(len(candidates)):
for j in range(i + 1, len(candidates)):
a = candidates[i]
b = candidates[j]
if (a % 21 == 0 or b % 21 == 0):
pair = (a, b)
if answer is None or sum(pair) > sum(answer):
answer = pair

if answer is None:
print(0, 0)
else:
print(answer[0], answer[1])