Задание EGEINF8AAE42: Пары и тройки в числовых данных

ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий

Открыть решение ↓ Ошибка или пожелание

Тип задачи: Пары и тройки в числовых данных.

Учебные темы: Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве.

Впишите правильный ответ.

Рисунок из условия ФИПИ

Задание выполняется с использованием прилагаемых файлов.

 

В файле содержится последовательность целых чисел. Её элементы могут принимать целые значения от – 100 000 до 100 000 включительно. Определите количество пар последовательности,
в которых элементы не равны, а абсолютное значение их разности делится на минимальный положительный элемент последовательности, кратный 33. Гарантируется, что такой элемент в последовательности есть. В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.

 

Рисунок из условия ФИПИ


i
СВОЙСТВА ЗАДАНИЯ
КЭС:
3.10 Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве
Тип ответа:Краткий ответ
Номер: 8AAE42
НЕ РЕШЕНО Ответить

Решение задания EGEINF8AAE42

Ответ: 33 164160

Решение.
Считываем исходный текстовый файл как последовательность целых чисел, сохраняя их порядок. В нём 10000 элементов; первой строки с количеством элементов нет.
Парой считаются только соседние элементы. При индексации Python от нуля перебираем i от 0 до len(a) − 2 и берём a[i], a[i + 1]. Всего проверяем 9999 пар. Пары могут пересекаться, а каждое начало рассматривается ровно один раз.
Сначала отбираем положительные элементы, кратные 33: x > 0 и x mod 33 = 0. Порог m — наименьший из них; существование такого элемента гарантировано условием.
Для исходного файла получаем m = 297 = 33 · 9. Этот элемент стоит на позиции 3987 при нумерации от единицы. Все меньшие положительные элементы файла не кратны 33.
Для пары x, y проверяем одновременно x ≠ y и |x − y| mod m = 0. Неравенство обязательно: нулевая разность делится на m, но равные элементы прямо исключены условием.
У подходящих пар считаем сумму x + y и выбираем максимальную сумму. Знак чисел не ограничен; делимость проверяем для модуля разности.
После обработки очередной пары count равно числу подходящих пар среди уже проверенных, а best хранит требуемую крайнюю сумму среди них. Для первой подходящей пары присваиваем её сумму; затем обновляем best. Начальное значение None позволяет корректно работать и с отрицательными суммами.
Сохраните скачанный файл рядом с программой под его исходным именем. Программа на Python:

with open("img1_1786621721.txt") as f:
    a = [int(line) for line in f]
m = min(x for x in a if x > 0 and x % 33 == 0)
count = 0
best = None
for i in range(len(a) - 1):
    x, y = a[i], a[i + 1]
    if x != y and abs(x - y) % m == 0:
        count += 1
        s = x + y
        best = s if best is None else max(best, s)
print(count, best)

Перебор исходного файла даёт count = 33, best = 164160.
Проверка: крайняя сумма достигается на соседних позициях 1726 и 1727: x = 90396, y = 73764, x + y = 164160.
Элементы не равны; |90396 − 73764| = 16632 = 297 · 56. Значит, эта пара проходит отбор.
Независимый повторный проход подтвердил все индексы отобранных пар, их количество и крайнюю сумму. Других соседних пар нет: диапазон начал охватывает весь файл без пропусков.
Поиск порога и просмотр пар требуют линейного времени O(n). Массив занимает O(n) памяти; счётчик и текущая крайняя сумма — постоянный объём.
Ответ: 33 164160.

Помочь улучшить сайт

Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF8AAE42.

Сообщение увидит только команда сайта: на странице оно не публикуется.

Комментарии к решению

Комментарии видны всем посетителям сайта.

Комментариев пока нет. Будьте первым.

Чтобы оставить комментарий, войдите или зарегистрируйтесь.