Максимальная сумма допустимой пары
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на $p=33$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \leq N \leq 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения задачи. Эффективная по времени программа должна работать за время, не превышающее линейное относительно $N$. Эффективная по памяти программа должна использовать не более $1$ Кбайт памяти, причём объём памяти не должен увеличиваться с ростом $N$.
Перед текстом программы кратко опишите алгоритм решения, укажите использованный язык программирования и его версию.
Условие как в банке ФИПИ — открыть и сверить
| Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на p = 33. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля. Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Пример входных данных: 5 66 12 99 100 99 Пример выходных данных для приведённого выше примера входных данных: 99 99 Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (66, 12), (66, 100), (99, 99). Наибольшая сумма получается в паре (99, 99). Эта пара допустима, так как число 99 встречается в исходной последовательности дважды. Напишите эффективную по времени и памяти программу для шешімдер этой тапсырма. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N. Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, 4 балл. Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, 3 балл. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, 2 балл. Вы можете сдать одну немесе две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет боьшая из двух оценок. Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
| ||
| |
Это задание с развёрнутым решением: ответом считается шешімнің барысын жазу, жол емес. Шешімді қағазға жазып, салыстырыңыз с разбором — там каждый шаг с обоснованием.
Талдауды ашу1Мягкая — с чего смотретьдеңгей 1 из 3
Разность двух чисел чётна тогда и только тогда, когда числа имеют одинаковую чётность. Какие максимальные элементы достаточно хранить для каждой чётности?
2Жетекші — қандай сандарды есептеудеңгей 2 из 3
Храните максимальное обработанное число каждой чётности и максимальное обработанное число каждой чётности, кратное $33$. Для очередного числа достаточно проверить одного подходящего ранее обработанного кандидата.
3Тікелей — іс жүзінде шешімдеңгей 3 из 3
Если текущее число кратно $33$, объединяйте его с максимальным ранее встреченным числом той же чётности. Иначе объединяйте его с максимальным ранее встреченным числом той же чётности, кратным $33$. После проверки обновите соответствующие максимумы.