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

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

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

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

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

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

Решение

1. Условие на чётность означает, что элементы пары должны иметь одинаковую чётность. При обработке чисел слева направо достаточно хранить максимальное ранее встреченное число каждой чётности.

2. Если текущее число кратно 33, второй элемент пары может быть любым ранее встреченным числом той же чётности. Если текущее число не кратно 33, второй элемент обязательно должен быть ранее встреченным числом той же чётности, кратным 33.

3. Для каждого из двух случаев проверяем возможную сумму с соответствующим максимальным кандидатом. Затем обновляем максимальное число данной чётности и, если число кратно 33, максимальное кратное число данной чётности.
O(N) по времени и O(1) по дополнительной памяти

4. Использованный язык: Python 3.11. Программа читает числа последовательно и не хранит всю последовательность.

5. Программа:

```python
n = int(input())

max_any = [None, None]
max_div = [None, None]
best_sum = -1
best_pair = (0, 0)

for _ in range(n):
    x = int(input())
    parity = x % 2

    if x % 33 == 0:
        y = max_any[parity]
    else:
        y = max_div[parity]

    if y is not None and x + y > best_sum:
        best_sum = x + y
        best_pair = (y, x)

    if max_any[parity] is None or x > max_any[parity]:
        max_any[parity] = x

    if x % 33 == 0:
        if max_div[parity] is None or x > max_div[parity]:
            max_div[parity] = x

print(best_pair[0], best_pair[1])
```

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

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

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

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

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

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

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

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

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

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

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

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

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

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