Максимальная сумма пары
Дана последовательность $N$ целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на $d = 200$, и по крайней мере одно из чисел пары делится на $p = 7$. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел $N$ ($2 \leq N \leq 10\,000$). В каждой из последующих $N$ строк записано одно натуральное число, не превышающее $10\,000$.
Напишите эффективную по времени и памяти программу для решения этой задачи. Программа должна работать за время $O(N)$ и использовать объём памяти, не зависящий от $N$ и $d$. Перед текстом программы кратко опишите алгоритм решения и укажите использованный язык программирования и его версию.
Условие как в банке ФИПИ — открыть и сверить
| Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на d = 200, и, по крайней мере, одно из чисел пары делится на p = 7. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля. Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Пример входных данных: 4 70 270 63 73 Пример выходных данных для приведённого выше примера входных данных: 270 63 Пояснение. Из данных четырёх чисел можно составить четыре различные пары, удовлетворяющие условию: (70, 63), (70, 73), (270, 63), (63, 73). Наибольшая сумма получается в паре (270, 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$, с другим остатком. После проверки добавляйте текущее число в обе структуры, если это необходимо.