ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Пары и тройки в числовых данных.
| КЭС: | 3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность 3.6 Язык программирования (Паскаль, Python, Java, C++, C#). Типы данных: целочисленные, вещественные, символьные, логические. Ветвления. Сложные условия. Циклы с условием. Циклы по переменной. Обработка данных, хранящихся в файлах. Текстовые и двоичные файлы. Файловые переменные (файловые указатели). Чтение из файла. Запись в файл. Разбиение задачи на подзадачи. Подпрограммы (процедуры и функции). Использование стандартной библиотеки языка программирования |
| Тип ответа: | Краткий ответ |
Ответ: 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.
| Номер | Первый элемент | Второй элемент | Сумма |
|---|---|---|---|
| 39 | 905 | 85 | 990 |
| 160 | 37 | 161 | 198 |
| 389 | 61 | 830 | 891 |
| 661 | 211 | 86 | 297 |
| 1099 | 13 | 680 | 693 |
| 1461 | 95 | 4 | 99 |
| 1598 | 2 | 97 | 99 |
| 1608 | 1 | 98 | 99 |
| 2064 | 9692 | 10 | 9702 |
| 2207 | 9653 | 49 | 9702 |
| 2406 | 91 | 8 | 99 |
| 2631 | 2 | 97 | 99 |
| 3505 | 1105 | 83 | 1188 |
| 3828 | 91 | 8 | 99 |
| 3933 | 678 | 15 | 693 |
| 4258 | 2 | 97 | 99 |
Наибольшая сумма достигается дважды: 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.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.