Максимальная пара с остатками
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на $d = 160$, и по крайней мере одно из чисел пары делится на $p = 7$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \le N \le 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел $N$ в $k$ раз время работы программы увеличивается не более чем в $k$ раз, а при увеличении параметра $d$ в $k$ раз время работы программы не увеличивается. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом $N$ и $d$.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Условие как в банке ФИПИ — открыть и сверить
| Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на d = 160, и, по крайней мере, одно из чисел пары делится на p = 7. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля. Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Пример входных данных: 4 70 230 63 73 Пример выходных данных для приведённого выше примера входных данных: 230 63 Пояснение. Из данных четырёх чисел можно составить четыре различные пары, удовлетворяющие условию: (70, 63), (70, 73), (230, 63), (63, 73). Наибольшая сумма получается в паре (230, 63). Напишите эффективную по времени и памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз, а при увеличении параметра d в k раз время работы программы не увеличивается. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N и d. Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, 4 балла. Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, в том числе память или время работы которой увеличивается не более чем в k раз при увеличении параметра d в k раз, Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, 2 балла. Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет боьшая из двух оценок. Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
| ||
| |
Это задание с развёрнутым решением: ответом считается запись хода решения, а не строка. Напишите решение на бумаге и сравните с разбором — там каждый шаг с обоснованием.
Открыть разбор1Мягкая — с чего смотретьуровень 1 из 3
Нужно обрабатывать числа по одному. Для текущего числа достаточно знать лучший подходящий элемент среди уже просмотренных чисел с другим остатком.
2Наводящая — какие числа считатьуровень 2 из 3
Для запроса максимума с остатком, отличным от текущего, храните два самых больших значения с различными остатками. Отдельно поддерживайте такую пару для чисел, делящихся на $7$.
3Прямая — фактически решениеуровень 3 из 3
Если текущее число делится на $7$, его можно объединить с максимальным ранее встреченным числом с другим остатком. Иначе его можно объединить только с максимальным ранее встреченным числом, делящимся на $7$, с другим остатком. После проверки добавьте текущее число в структуры максимумов.