ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Пары и тройки в числовых данных.
| КЭС: | 3.10 Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве |
| Тип ответа: | Краткий ответ |
Ответ: 200 173308
Решение.
Считываем исходный текстовый файл как последовательность целых чисел, сохраняя их порядок. В нём 10000 элементов; первой строки с количеством элементов нет.
Парой считаются только соседние элементы. При индексации Python от нуля перебираем i от 0 до len(a) − 2 и берём a[i], a[i + 1]. Всего проверяем 9999 пар. Пары могут пересекаться, а каждое начало рассматривается ровно один раз.
Первым проходом находим минимальный элемент всего файла: m = 8. Он стоит на позиции 9564 при нумерации от единицы. Здесь минимум берётся по всем элементам, до отбора пар.
Для каждой соседней пары x, y проверяем x mod 20 + y mod 20 = m. Сумма двух отдельных остатков может отличаться от остатка суммы, поэтому не заменяем это условие на (x + y) mod 20 = m.
У всех подходящих пар считаем сумму самих чисел x + y; выбираем максимальную такую сумму.
После обработки очередной пары count равно числу подходящих пар среди уже проверенных, а best хранит требуемую крайнюю сумму среди них. Для первой подходящей пары присваиваем её сумму; затем обновляем best. Начальное значение None позволяет корректно работать и с отрицательными суммами.
Сохраните скачанный файл рядом с программой под его исходным именем. Программа на Python:
with open("img1_1786621842.txt") as f:
a = [int(line) for line in f]
m = min(a)
count = 0
best = None
for i in range(len(a) - 1):
x, y = a[i], a[i + 1]
if x % 20 + y % 20 == m:
count += 1
s = x + y
best = s if best is None else max(best, s)
print(count, best)Перебор исходного файла даёт count = 200, best = 173308.
Проверка: крайняя сумма достигается на соседних позициях 6573 и 6574: x = 89827, y = 83481, x + y = 173308.
Остатки равны 7 и 1; их сумма 7 + 1 = 8, поэтому пара подходит.
Независимый повторный проход подтвердил все индексы отобранных пар, их количество и крайнюю сумму. Других соседних пар нет: диапазон начал охватывает весь файл без пропусков.
Поиск порога и просмотр пар требуют линейного времени O(n). Массив занимает O(n) памяти; счётчик и текущая крайняя сумма — постоянный объём.
Ответ: 200 173308.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFE5D71A.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.