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

1. Обрабатываем числа слева направо. Для каждого уже обработанного числа достаточно хранить несколько лучших кандидатов: два максимальных числа с различными остатками и два максимальных числа, делящихся на 7, также с различными остатками. Если два максимальных значения имеют одинаковый остаток, сохраняем только большее из них.

2. Пусть текущее число равно x, а его остаток по модулю 160 равен r. Если x делится на 7, то второй элемент пары может быть любым ранее обработанным числом с остатком, не равным r. Если x не делится на 7, второй элемент должен делиться на 7 и иметь остаток, не равный r.
x mod 7=0⇒y mod 160≠r;x mod 7≠0⇒y mod 7=0, y mod 160≠r

3. Из двух сохранённых максимумов выбираем первый, если его остаток отличается от r, иначе второй. Проверяем полученную сумму и при необходимости обновляем лучшую пару.

4. После проверки текущего числа обновляем общий набор двух максимумов и, если число делится на 7, набор двух максимумов среди чисел, делящихся на 7. В каждой структуре хранится постоянное число элементов, поэтому память не зависит от N и d.

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

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

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