Задание 27 ЕГЭ по информатике · 5D03DA
Программа и описание алгоритмаВысокаяКЭС 3.2КЭС 3.3
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на p=27. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Напишите эффективную по времени и памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Напишите эффективную по времени и памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Разность двух чисел чётна тогда и только тогда, когда числа имеют одинаковую чётность. Какие максимальные элементы достаточно хранить для каждой чётности?
- Для каждой чётности храните два наибольших числа, кратных 27, и наибольшее число, не кратное 27. Затем проверьте пары из числа, кратного 27, с числом той же чётности.
- Обрабатывайте числа по одному. Для каждой чётности обновляйте два максимальных кратных 27 и максимум среди остальных. В конце сравните суммы: два кратных числа одной чётности и максимальное кратное число с максимальным некратным числом той же чётности.
Решение
1. Разность элементов пары должна быть чётной, поэтому элементы пары должны иметь одинаковую чётность.
2. Возможны два типа допустимых пар: оба числа кратны 27 либо одно число кратно 27, а второе не кратно 27. В обоих случаях числа должны иметь одинаковую чётность.
3. При последовательном просмотре достаточно хранить для каждой чётности два наибольших числа, кратных 27, и наибольшее число, не кратное 27. Этого достаточно, поскольку сумма максимизируется при выборе наибольших подходящих элементов.
4. Для каждой чётности проверяем сумму двух наибольших чисел, кратных 27, а также сумму наибольшего числа, кратного 27, и наибольшего числа, не кратного 27.
5. Если ни одна допустимая пара не найдена, выводим 0 0. Иначе выводим элементы пары с максимальной суммой.
6. Алгоритм выполняет один проход по входным данным, поэтому его временная сложность равна O(N), а объём используемой памяти — O(1).
7. Пример программы на Python 3.11:
2. Возможны два типа допустимых пар: оба числа кратны 27 либо одно число кратно 27, а второе не кратно 27. В обоих случаях числа должны иметь одинаковую чётность.
3. При последовательном просмотре достаточно хранить для каждой чётности два наибольших числа, кратных 27, и наибольшее число, не кратное 27. Этого достаточно, поскольку сумма максимизируется при выборе наибольших подходящих элементов.
4. Для каждой чётности проверяем сумму двух наибольших чисел, кратных 27, а также сумму наибольшего числа, кратного 27, и наибольшего числа, не кратного 27.
5. Если ни одна допустимая пара не найдена, выводим 0 0. Иначе выводим элементы пары с максимальной суммой.
6. Алгоритм выполняет один проход по входным данным, поэтому его временная сложность равна O(N), а объём используемой памяти — O(1).
7. Пример программы на Python 3.11:
n = int(input())
best_div = [[-1, -1], [-1, -1]]
best_other = [-1, -1]
for _ in range(n):
x = int(input())
parity = x % 2
if x % 27 == 0:
if x >= best_div[parity][0]:
best_div[parity][1] = best_div[parity][0]
best_div[parity][0] = x
elif x > best_div[parity][1]:
best_div[parity][1] = x
elif x > best_other[parity]:
best_other[parity] = x
answer = None
for parity in (0, 1):
a, b = best_div[parity]
c = best_other[parity]
if b != -1:
answer = max(answer, (a + b, a, b)) if answer else (a + b, a, b)
if c != -1:
answer = max(answer, (a + c, a, c)) if answer else (a + c, a, c)
if answer is None:
print(0, 0)
else:
print(answer[1], answer[2])Частые ошибки
- Проверяют только пары из двух чисел, кратных 27, и пропускают пары, где второе число не кратно 27.
- Сравнивают чётность самих чисел вместо проверки одинаковой чётности.
- Используют массив всех входных чисел, нарушая требование постоянного объёма памяти.
- Не обрабатывают случай отсутствия подходящих пар.
Источник: Открытый банк ФИПИ
Похожие задания
27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 335BFF27Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4…Программа и описание алгоритма · 37B02227На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени…Программа и описание алгоритма · 39143827Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в…Программа и описание алгоритма · 559E6927Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 5…Программа и описание алгоритма · 6A655827На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой…Программа и описание алгоритма · 6FF64727Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 7BD73827Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять рядом…Программа и описание алгоритма · 8180D7
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.