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

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

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

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

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

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

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

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

 

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

 

Скачать файл задания (TXT, ФИПИ)


i
СВОЙСТВА ЗАДАНИЯ
КЭС:
3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность
3.6 Язык программирования (Паскаль, Python, Java, C++, C#). Типы данных: целочисленные, вещественные, символьные, логические. Ветвления. Сложные условия. Циклы с условием. Циклы по переменной. Обработка данных, хранящихся в файлах. Текстовые и двоичные файлы. Файловые переменные (файловые указатели). Чтение из файла. Запись в файл. Разбиение задачи на подзадачи. Подпрограммы (процедуры и функции). Использование стандартной библиотеки языка программирования
Тип ответа:Краткий ответ
Номер: FCE3BE
НЕ РЕШЕНО Ответить

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

Ответ: 16 9702

Решение.
Используем исходный текстовый файл задания. В нём записаны сами элементы последовательности; отдельного числа с её длиной в начале файла нет. Сохраните файл рядом с программой под именем 1_17.txt.
Сначала среди всех элементов, а не только среди подходящих пар, находим наибольшее двузначное число M. Число является двузначным, если 10 ≤ x ≤ 99.
При чтении исходного файла получаем N = 4403, M = 99. Проверяем все N − 1 = 4402 соседних пар. Для пары (x, y) должны одновременно выполняться два требования:
1. Ровно одно из чисел двузначное. Обозначим условия двузначности через p и q. Тогда p ≠ q: значения истина-истина и ложь-ложь не подходят.
2. Сумма s = x + y делится на M без остатка: s mod M = 0.
Пара учитывается один раз, по позиции первого элемента. Один элемент может входить в две соседние пары: это разные пары, поэтому пропускать следующую позицию нельзя.
Все найденные пары приведены ниже. Номер — позиция первого элемента, начиная с 1.

НомерПервый элементВторой элементСумма
3990585990
16037161198
38961830891
66121186297
109913680693
146195499
159829799
160819899
20649692109702
22079653499702
240691899
263129799
35051105831188
382891899
393367815693
425829799

Наибольшая сумма достигается дважды: 9692 + 10 = 9702 и 9653 + 49 = 9702. В каждой паре только второе число двузначное; 9702 = 99 · 98, поэтому делимость также выполнена.
Программа на Python:

with open('1_17.txt', encoding='utf-8-sig') as f:
    a = [int(s) for s in f.read().split()]

limit = max(x for x in a if 10 <= x <= 99)
count = 0
best = None
for i in range(len(a) - 1):
    x, y = a[i], a[i + 1]
    one_two_digit = (10 <= x <= 99) != (10 <= y <= 99)
    if one_two_digit and (x + y) % limit == 0:
        count += 1
        if best is None or x + y > best:
            best = x + y
print(count, best)

Результат запуска на исходном файле: 16 9702.
Получено 16 подходящих пар.
Проверка полноты. Цикл посещает каждую допустимую начальную позицию ровно один раз, включая первую и последнюю. После каждой итерации счётчик равен числу подходящих уже просмотренных окон, а best хранит нужное крайнее значение среди них. Обновление выполняется только после проверки всех требований, поэтому итог учитывает в точности нужные окна.
Время работы линейно по числу элементов: один просмотр для порога и один для окон. Список a занимает O(N) памяти; дополнительные переменные требуют O(1).
Ответ: 16 9702.

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

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

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

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

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

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

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