Задание 27 ЕГЭ по информатике · BCE6F1
Программа и описание алгоритмаВысокаяКЭС 3.2КЭС 3.3
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на 14.
В первой строке входных данных задаётся количество чисел N (1≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. Программа должна вывести количество пар, в которых произведение элементов кратно 14.
Пример входных данных:
4
2
6
7
21
Пример выходных данных:
4
Требуется написать эффективную по времени и по памяти программу. Алгоритм должен работать за время O(N), а используемая память не должна зависеть от N и не должна превышать 1 килобайт. Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.
В первой строке входных данных задаётся количество чисел N (1≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. Программа должна вывести количество пар, в которых произведение элементов кратно 14.
Пример входных данных:
4
2
6
7
21
Пример выходных данных:
4
Требуется написать эффективную по времени и по памяти программу. Алгоритм должен работать за время O(N), а используемая память не должна зависеть от N и не должна превышать 1 килобайт. Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Разложите условие делимости произведения на 14=2⋅7: в паре должен присутствовать множитель, содержащий двойку, и множитель, содержащий семёрку.
- При последовательном чтении храните количества уже обработанных чисел, кратных 2, 7 и 14. Для нового числа посчитайте подходящие пары с ранее прочитанными числами.
- Если новое число чётное, к ответу добавляется количество ранее встреченных чисел, кратных 7. Если новое число кратно 7, добавляется количество ранее встреченных чисел, кратных 2. Если новое число кратно 14, пересечение посчитано дважды, поэтому количество ранее встреченных чисел, кратных 14, нужно вычесть.
Решение
1. Для произведения двух чисел быть кратным 14, в произведении должны присутствовать множители 2 и 7. При обработке очередного числа считаем только пары с уже прочитанными числами, поэтому каждая пара учитывается ровно один раз.
14=2⋅7
2. Если текущее число чётное, оно уже содержит множитель 2, поэтому ему подходят все предыдущие числа, кратные 7. Если текущее число кратно 7, ему подходят все предыдущие числа, кратные 2.
3. Когда текущее число кратно 14, предыдущие числа, кратные 14, были посчитаны в обеих группах. Их нужно вычесть один раз.
Δ=[x mod 2=0]⋅c7+[x mod 7=0]⋅c2−[x mod 14=0]⋅c14
4. После подсчёта пар обновляем количества чисел, кратных 2, 7 и 14. Все счётчики занимают постоянный объём памяти, а каждое число обрабатывается за постоянное время, поэтому сложность алгоритма равна O(N) по времени и O(1) по памяти.
T(N)=O(N),M(N)=O(1)
5. Пример реализации на Python 3.
6. Код:
n = int(input()) c2 = 0 c7 = 0 c14 = 0 answer = 0 for _ in range(n):
x = int(input()) if x % 2 == 0:
answer += c7 if x % 7 == 0:
answer += c2 if x % 14 == 0:
answer -= c14 if x % 2 == 0:
c2 += 1 if x % 7 == 0:
c7 += 1 if x % 14 == 0:
c14 += 1 print(answer)
14=2⋅7
2. Если текущее число чётное, оно уже содержит множитель 2, поэтому ему подходят все предыдущие числа, кратные 7. Если текущее число кратно 7, ему подходят все предыдущие числа, кратные 2.
3. Когда текущее число кратно 14, предыдущие числа, кратные 14, были посчитаны в обеих группах. Их нужно вычесть один раз.
Δ=[x mod 2=0]⋅c7+[x mod 7=0]⋅c2−[x mod 14=0]⋅c14
4. После подсчёта пар обновляем количества чисел, кратных 2, 7 и 14. Все счётчики занимают постоянный объём памяти, а каждое число обрабатывается за постоянное время, поэтому сложность алгоритма равна O(N) по времени и O(1) по памяти.
T(N)=O(N),M(N)=O(1)
5. Пример реализации на Python 3.
6. Код:
n = int(input()) c2 = 0 c7 = 0 c14 = 0 answer = 0 for _ in range(n):
x = int(input()) if x % 2 == 0:
answer += c7 if x % 7 == 0:
answer += c2 if x % 14 == 0:
answer -= c14 if x % 2 == 0:
c2 += 1 if x % 7 == 0:
c7 += 1 if x % 14 == 0:
c14 += 1 print(answer)
Частые ошибки
- Перебирать все пары, получая сложность $O(N^2)$.
- Учитывать только пары, в которых одно число кратно $14$, хотя множители $2$ и $7$ могут находиться в разных числах.
- Не вычитать числа, кратные $14$, когда текущее число также кратно $14$: такие пары считаются дважды.
- Хранить всю последовательность, нарушая требование постоянного объёма памяти.
Источник: Открытый банк ФИПИ
Похожие задания
27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 7BD73827Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять рядом…Программа и описание алгоритма · 8180D727Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 8F133027Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в…Программа и описание алгоритма · 902B8427На вход программе подаются строчные английские буквы. Ввод этих символов заканчивается точкой (другие…Программа и описание алгоритма · C0417927Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять рядом…Программа и описание алгоритма · E3E82427На вход программе подаются сведения о пассажирах, сдавших свой багаж в камеру хранения. В первой строке…Программа и описание алгоритма · E9F6D627Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3…Программа и описание алгоритма · ED6EB9
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.