Решение: Максимальная сумма допустимой пары
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на $p=33$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \leq N \leq 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения задачи. Эффективная по времени программа должна работать за время, не превышающее линейное относительно $N$. Эффективная по памяти программа должна использовать не более $1$ Кбайт памяти, причём объём памяти не должен увеличиваться с ростом $N$.
Перед текстом программы кратко опишите алгоритм решения, укажите использованный язык программирования и его версию.
Решение по шагам
5 шаговУсловие на чётность означает, что элементы пары должны иметь одинаковую чётность. При обработке чисел слева направо достаточно хранить максимальное ранее встреченное число каждой чётности.
Если текущее число кратно $33$, второй элемент пары может быть любым ранее встреченным числом той же чётности. Если текущее число не кратно $33$, второй элемент обязательно должен быть ранее встреченным числом той же чётности, кратным $33$.
Для каждого из двух случаев проверяем возможную сумму с соответствующим максимальным кандидатом. Затем обновляем максимальное число данной чётности и, если число кратно $33$, максимальное кратное число данной чётности.
$$O(N)\text{ по времени и }O(1)\text{ по дополнительной памяти}$$Использованный язык: Python 3.11. Программа читает числа последовательно и не хранит всю последовательность.
Программа:
$$```python n = int(input()) max_any = [None, None] max_div = [None, None] best_sum = -1 best_pair = (0, 0) for _ in range(n): x = int(input()) parity = x % 2 if x % 33 == 0: y = max_any[parity] else: y = max_div[parity] if y is not None and x + y > best_sum: best_sum = x + y best_pair = (y, x) if max_any[parity] is None or x > max_any[parity]: max_any[parity] = x if x % 33 == 0: if max_div[parity] is None or x > max_div[parity]: max_div[parity] = x print(best_pair[0], best_pair[1]) ```$$Алгоритм выполняется за $O(N)$ времени и использует $O(1)$ дополнительной памяти; при отсутствии подходящей пары выводится `0 0`.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Хранение всей последовательности, из-за чего нарушается требование по памяти.
Проверка только делимости на $33$ без проверки одинаковой чётности.
Обновление максимумов до проверки пары, из-за чего число может быть использовано само с собой.
Попытка перебирать все пары, что имеет сложность $O(N^2)$.