Решение: Максимальная пара с делителем 27
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на $p = 27$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \leq N \leq 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел $N$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом $N$.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение по шагам
7 шаговРазность элементов пары должна быть чётной, поэтому элементы пары должны иметь одинаковую чётность.
Возможны два типа допустимых пар: оба числа кратны 27 либо одно число кратно 27, а второе не кратно 27. В обоих случаях числа должны иметь одинаковую чётность.
При последовательном просмотре достаточно хранить для каждой чётности два наибольших числа, кратных 27, и наибольшее число, не кратное 27. Этого достаточно, поскольку сумма максимизируется при выборе наибольших подходящих элементов.
Для каждой чётности проверяем сумму двух наибольших чисел, кратных 27, а также сумму наибольшего числа, кратного 27, и наибольшего числа, не кратного 27.
Если ни одна допустимая пара не найдена, выводим 0 0. Иначе выводим элементы пары с максимальной суммой.
Алгоритм выполняет один проход по входным данным, поэтому его временная сложность равна O(N), а объём используемой памяти — O(1).
Пример программы на Python 3.11:
$$n = int(input()) best_div = [[-1, -1], [-1, -1]] best_other = [-1, -1] for _ in range(n): x = int(input()) parity = x % 2 if x % 27 == 0: if x >= best_div[parity][0]: best_div[parity][1] = best_div[parity][0] best_div[parity][0] = x elif x > best_div[parity][1]: best_div[parity][1] = x elif x > best_other[parity]: best_other[parity] = x answer = None for parity in (0, 1): a, b = best_div[parity] c = best_other[parity] if b != -1: answer = max(answer, (a + b, a, b)) if answer else (a + b, a, b) if c != -1: answer = max(answer, (a + c, a, c)) if answer else (a + c, a, c) if answer is None: print(0, 0) else: print(answer[1], answer[2])$$Решение: для каждой чётности хранить два максимальных числа, кратных 27, и одно максимальное число, не кратное 27; затем выбрать пару с максимальной суммой. Сложность O(N) по времени и O(1) по памяти.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только пары из двух чисел, кратных 27, и пропускают пары, где второе число не кратно 27.
Сравнивают чётность самих чисел вместо проверки одинаковой чётности.
Хранят только одно максимальное число, кратное 27, из-за чего невозможно корректно составить пару из двух кратных чисел.
Используют массив всех входных чисел, нарушая требование постоянного объёма памяти.
Не обрабатывают случай отсутствия подходящих пар.