Задание 27 ЕГЭ по информатике · 233FD1
Программа и описание алгоритмаВысокаяКЭС 3.2КЭС 3.3
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4: разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 11.
В первой строке входных данных задаётся количество чисел N (4≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна вывести одно число — количество пар элементов, находящихся в последовательности на расстоянии не меньше 4, в которых произведение элементов кратно 11.
Требуется написать эффективную по времени и памяти программу. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.
В первой строке входных данных задаётся количество чисел N (4≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна вывести одно число — количество пар элементов, находящихся в последовательности на расстоянии не меньше 4, в которых произведение элементов кратно 11.
Требуется написать эффективную по времени и памяти программу. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Когда произведение двух чисел делится на 11? Как учитывать пары с индексами, отличающимися менее чем на 4?
- Достаточно знать, делится ли число на 11. При обработке очередного элемента учитывайте только уже просмотренные элементы, расположенные не ближе чем на 4 позиции.
- Храните количество чисел, кратных 11, среди элементов, которые уже стали допустимыми партнёрами текущего числа, и количество некратных. Для текущего числа, кратного 11, добавляйте первое количество, иначе добавляйте второе.
Решение
1. Произведение двух целых чисел делится на 11, если хотя бы один из множителей делится на 11. Поэтому для каждого числа достаточно хранить только признак делимости на 11.
2. При обработке элемента с индексом i допустимыми являются элементы с индексами не больше i−4. Элемент с индексом i−4 именно в этот момент добавляется в счётчики допустимых предыдущих элементов.
3. Если текущий элемент делится на 11, он образует подходящую пару с каждым допустимым предыдущим элементом. Иначе подходящую пару он образует только с допустимыми предыдущими элементами, кратными 11.
4. Для первых четырёх элементов допустимых предыдущих элементов нет, поэтому счётчики не изменяются. Каждый элемент добавляется в счётчики ровно один раз, а каждая пара учитывается ровно при обработке элемента с большим индексом.
5. Алгоритм выполняется за время O(N) и использует O(1) дополнительной памяти, поскольку хранит только несколько счётчиков и последние четыре значения.
6. Язык программирования: Python 3.
7. Программа:
2. При обработке элемента с индексом i допустимыми являются элементы с индексами не больше i−4. Элемент с индексом i−4 именно в этот момент добавляется в счётчики допустимых предыдущих элементов.
3. Если текущий элемент делится на 11, он образует подходящую пару с каждым допустимым предыдущим элементом. Иначе подходящую пару он образует только с допустимыми предыдущими элементами, кратными 11.
4. Для первых четырёх элементов допустимых предыдущих элементов нет, поэтому счётчики не изменяются. Каждый элемент добавляется в счётчики ровно один раз, а каждая пара учитывается ровно при обработке элемента с большим индексом.
5. Алгоритм выполняется за время O(N) и использует O(1) дополнительной памяти, поскольку хранит только несколько счётчиков и последние четыре значения.
6. Язык программирования: Python 3.
7. Программа:
from collections import deque
n = int(input())
window = deque()
count_div11 = 0
count_not_div11 = 0
answer = 0
for i in range(n):
x = int(input())
if i >= 4:
old = window.popleft()
if old % 11 == 0:
count_div11 += 1
else:
count_not_div11 += 1
if x % 11 == 0:
answer += count_div11 + count_not_div11
else:
answer += count_div11
window.append(x)
print(answer)Частые ошибки
- Проверять все пары двойным циклом и получать время $O(N^2)$.
- Учитывать элементы с индексами $i-1$, $i-2$ или $i-3$, хотя они не удовлетворяют условию расстояния.
- Считать подходящими только пары, в которых оба числа делятся на 11; достаточно делимости хотя бы одного множителя.
- Добавлять текущий элемент в счётчики до подсчёта ответа, из-за чего может быть учтена пара элемента с самим собой.
- Хранить весь массив, нарушая требование постоянной памяти.
Источник: Открытый банк ФИПИ
Похожие задания
27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 04D7CD27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 0B12A627На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары…Программа и описание алгоритма · 195BE627Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 26775227Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 2931D927Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3…Программа и описание алгоритма · 29FE8627Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4…Программа и описание алгоритма · 2C4C0127Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 335BFF
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.