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