Задание 27 ЕГЭ по информатике · 335BFF

Программа и описание алгоритмаВысокаяКЭС 3.2КЭС 3.3

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на d=200, и по крайней мере одно из чисел пары делится на p=7. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Напишите эффективную по времени и памяти программу для решения этой задачи. Программа должна работать за время O(N) и использовать объём памяти, не зависящий от N и d. Перед текстом программы кратко опишите алгоритм решения и укажите использованный язык программирования и его версию.

Развёрнутый ответ: проверяется по критериям ФИПИ.

Подсказки (3)

Для каждого очередного числа достаточно знать лучший подходящий элемент среди уже прочитанных чисел. Как быстро искать максимум с остатком, отличным от остатка текущего числа?
Храните два наибольших числа с различными остатками: отдельно среди всех чисел и отдельно среди чисел, кратных 7. Для исключения одного остатка достаточно проверить эти два значения.
Если текущее число кратно 7, соединяйте его с наибольшим предыдущим числом с другим остатком. Иначе соединяйте его с наибольшим предыдущим числом, кратным 7, с другим остатком. После проверки добавляйте текущее число в обе структуры, если это необходимо.

Решение

1. Будем обрабатывать числа последовательно. Для каждой пары один элемент будет текущим, а второй уже встретится ранее, поэтому каждая пара будет рассмотрена ровно один раз.

2. Если текущее число делится на 7, второй элемент пары может быть любым предыдущим числом, но его остаток по модулю 200 должен отличаться от остатка текущего числа. Для такого поиска достаточно хранить два наибольших предыдущих числа с различными остатками.

3. Если текущее число не делится на 7, второй элемент обязательно должен быть предыдущим числом, делящимся на 7. Поэтому отдельно храним два наибольших таких числа с различными остатками.

4. Для каждого из двух наборов двух максимумов проверяем первый элемент. Если его остаток совпал с остатком текущего числа, используем второй элемент. Это даёт лучший допустимый партнёр.

5. После проверки текущего числа обновляем максимумы. В каждой структуре хранятся только два числа с различными остатками, поэтому объём памяти постоянен.

6. Время работы программы составляет O(N), поскольку каждое число обрабатывается за постоянное число операций. Память имеет сложность O(1) и не зависит от N и d.

Частые ошибки

Хранить все входные числа или массив размером $N$, что нарушает требование по памяти.
Проверять все пары, получая сложность $O(N^2)$.
Не учитывать различие остатков от деления на $200$.
При совпадении остатка с первым максимумом не переходить ко второму максимуму.
Разрешить число само с собой, если оно уже было добавлено в структуру до проверки текущего числа.

Источник: Открытый банк ФИПИ

Предыдущее Следующее Все задания №27

Нужен репетитор по информатике?

Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.

Репетиторы по информатике

Готовьтесь к ЕГЭ по информатике в Precettore

Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.

Начать бесплатно Я репетитор

Задание 27 ЕГЭ по информатике · 335BFF

Похожие задания

Нужен репетитор по информатике?

Готовьтесь к ЕГЭ по информатике в Precettore