Шешімі: Максимальная сумма пары
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на $p = 21$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \leq N \leq 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения этой задачи. Программа должна работать за время $O(N)$ и использовать объём памяти, не зависящий от $N$ и не превышающий 1 Кбайт.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Шешім по шагам
6 қадамРазность элементов пары должна быть чётной, поэтому оба элемента должны иметь одинаковую чётность. Обрабатываем отдельно чётные и нечётные числа.
$$a \bmod 2 = b \bmod 2$$Для каждой чётности сохраняем два наибольших числа среди всех чисел и два наибольших числа, кратных $21$. Два элемента нужны потому, что элементы пары должны быть различными элементами последовательности, даже если их значения совпадают.
Любая оптимальная пара состоит из сохранённых кандидатов: если элемент не входит в два наибольших числа своей чётности или в два наибольших числа, кратных $21$, его можно заменить на более крупный допустимый элемент, не уменьшая сумму.
Перебираем все пары сохранённых кандидатов одной чётности. Оставляем только пары, в которых хотя бы один элемент делится на $21$, и выбираем пару с наибольшей суммой.
Алгоритм выполняет постоянное число операций для каждого из $N$ чисел, поэтому работает за $O(N)$ и использует $O(1)$ памяти.
Пример программы на 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])$$Вывести описание однопроходного алгоритма и программу на Python 3, хранящую постоянное число кандидатов для каждой чётности.
Бұл жауап талдау нәтижесінде алынды, бірақ банктің ресми кілтімен тексерілген жоқ — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверять только значения чисел, а не количество их вхождений: пара из двух одинаковых значений допустима только при наличии двух соответствующих элементов.
Рассматривать только пары, в которых оба числа делятся на $21$, хотя по условию достаточно делимости хотя бы одного элемента.
Не разделять числа по чётности.
Сохранять всю последовательность, нарушая ограничение по памяти.
Использовать двойной перебор всех пар, что даёт сложность $O(N^2)$.