Задание 27 ЕГЭ по информатике · 195BE6
Программа и описание алгоритмаВысокаяКЭС 3.2КЭС 3.3
На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности ai и aj, такие что i<j и ai>aj. Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m=120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
В первой строке входных данных задаётся количество чисел n (2≤n≤12 000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
В первой строке входных данных задаётся количество чисел n (2≤n≤12 000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Какие сведения о уже обработанных числах нужны, чтобы быстро подобрать пару к очередному числу?
- Для суммы, делящейся на 120, остатки двух чисел должны в сумме давать остаток 0 по модулю 120. Для каждого остатка храните максимальный ранее встреченный элемент.
- При обработке очередного числа x найдите среди сохранённых чисел остатка (120−x mod 120) mod 120 максимальное значение y. Если y>x, сравните сумму x+y с текущим максимумом. После этого обновите максимум для остатка x mod 120.
Решение
1. Обрабатываем последовательность слева направо. Поэтому все сохранённые элементы автоматически имеют индекс меньше индекса текущего элемента, что обеспечивает условие i<j.
2. Если текущий элемент равен x, то для делимости суммы на 120 предыдущий элемент y должен иметь остаток (120−x mod 120) mod 120.
y mod 120=(120−x mod 120) mod 120
3. Для каждого остатка храним только максимальный ранее встреченный элемент. Это достаточно: среди элементов с одним и тем же остатком больший элемент образует с текущим x большую сумму. Если максимальный элемент больше x, условие ai>aj выполнено.
4. Для найденной подходящей пары сравниваем сумму с максимальной найденной ранее суммой и сохраняем пару с большей суммой.
5. После проверки текущего элемента обновляем максимальное значение для его остатка. Используется массив из 120 элементов, поэтому дополнительная память не зависит от n, а время работы составляет O(n).
6. Язык программирования: Python 3.11.
7. Программа:
2. Если текущий элемент равен x, то для делимости суммы на 120 предыдущий элемент y должен иметь остаток (120−x mod 120) mod 120.
y mod 120=(120−x mod 120) mod 120
3. Для каждого остатка храним только максимальный ранее встреченный элемент. Это достаточно: среди элементов с одним и тем же остатком больший элемент образует с текущим x большую сумму. Если максимальный элемент больше x, условие ai>aj выполнено.
4. Для найденной подходящей пары сравниваем сумму с максимальной найденной ранее суммой и сохраняем пару с большей суммой.
5. После проверки текущего элемента обновляем максимальное значение для его остатка. Используется массив из 120 элементов, поэтому дополнительная память не зависит от n, а время работы составляет O(n).
6. Язык программирования: Python 3.11.
7. Программа:
m = 120
max_by_rem = [-1] * m
best_sum = -1
best_pair = (0, 0)
n = int(input())
for _ in range(n):
x = int(input())
need = (m - x % m) % m
y = max_by_rem[need]
if y > x and y + x > best_sum:
best_sum = y + x
best_pair = (y, x)
rem = x % m
if x > max_by_rem[rem]:
max_by_rem[rem] = x
print(best_pair[0], best_pair[1])Частые ошибки
- Не проверять условие $a_i > a_j$.
- Обновлять данные о текущем числе до проверки пары, из-за чего число может быть использовано само с собой.
- Хранить минимум вместо максимума для каждого остатка.
- Перебирать все пары, получая сложность $O(n^2)$.
- Искать только пары с нужными остатками, но не учитывать порядок элементов.
Источник: Открытый банк ФИПИ
Похожие задания
27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 04D7CD27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 0B12A627Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4…Программа и описание алгоритма · 233FD127Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 26775227Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 2931D927Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3…Программа и описание алгоритма · 29FE8627Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4…Программа и описание алгоритма · 2C4C0127Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 335BFF
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.