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

1. Разность двух чисел чётна тогда и только тогда, когда числа имеют одинаковую чётность. Поэтому достаточно рассматривать отдельно пары чётных и пары нечётных чисел.

2. При обработке очередного числа x возможная подходящая пара должна содержать либо само число x, если оно делится на 19, либо ранее встреченное число той же чётности, делящееся на 19.

3. Чтобы получить максимальную сумму с текущим числом, достаточно хранить для каждой чётности максимальное число вообще и максимальное число, кратное 19. Все эти значения можно обновлять после проверки пар с текущим числом.

4. Если x кратно 19, его можно объединить с максимальным ранее встреченным числом той же чётности. Если среди ранее обработанных чисел той же чётности есть число, кратное 19, его можно объединить с x независимо от делимости x на 19.

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

6. Программа на Python 3:

7. ```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])
```