Задание 27 ЕГЭ по информатике · 559E69
Программа и описание алгоритмаВысокаяКЭС 3.2КЭС 3.3
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на 74.
В первой строке входных данных задаётся количество чисел N (1≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000.
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 74.
Пример входных данных:
4
2
6
37
111
Пример выходных данных для приведённого выше примера входных данных:
4
Из четырёх заданных чисел можно составить 6 попарных произведений: 2⋅6, 2⋅37, 2⋅111, 6⋅37, 6⋅111, 37⋅111. Из них на 74 делятся 4 произведения: 2⋅37=74, 2⋅111=222, 6⋅37=222, 6⋅111=666.
Требуется написать эффективную по времени и по памяти программу. При увеличении количества исходных чисел N в k раз время работы программы должно увеличиваться не более чем в k раз. Память, необходимая для хранения всех переменных программы, не должна превышать 1 килобайта и не должна увеличиваться с ростом N.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
В первой строке входных данных задаётся количество чисел N (1≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000.
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 74.
Пример входных данных:
4
2
6
37
111
Пример выходных данных для приведённого выше примера входных данных:
4
Из четырёх заданных чисел можно составить 6 попарных произведений: 2⋅6, 2⋅37, 2⋅111, 6⋅37, 6⋅111, 37⋅111. Из них на 74 делятся 4 произведения: 2⋅37=74, 2⋅111=222, 6⋅37=222, 6⋅111=666.
Требуется написать эффективную по времени и по памяти программу. При увеличении количества исходных чисел N в k раз время работы программы должно увеличиваться не более чем в k раз. Память, необходимая для хранения всех переменных программы, не должна превышать 1 килобайта и не должна увеличиваться с ростом N.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Разложите 74 на простые множители: 74=2⋅37. Какие свойства двух чисел могут обеспечить делимость их произведения на 74?
- Достаточно учитывать, делится ли число на 2, на 37 или на 74. Обрабатывайте числа последовательно и храните только несколько счётчиков.
- Для числа, кратного 74, подходят все ранее обработанные числа. Для числа, кратного 37, но не 2, подходят ранее обработанные чётные числа. Для чётного числа, не кратного 37, подходят ранее обработанные числа, кратные 37.
Решение
1. Представим число 74 как произведение взаимно простых множителей:
74=2⋅37
2. При последовательной обработке очередного числа достаточно знать количество ранее обработанных чисел четырёх типов: всех чисел; чётных чисел; чисел, кратных 37; чисел, кратных 74.
3. Если текущее число кратно 74, его произведение с любым предыдущим числом кратно 74. Если число кратно 37, но нечётно, ему в пару нужно предыдущее чётное число. Если число чётное, но не кратно 37, ему в пару нужно предыдущее число, кратное 37. Для остальных чисел подходящих пар нет.
4. После подсчёта подходящих пар обновляются счётчики типов текущего числа. Все операции выполняются за постоянное время для каждого элемента.
5. Алгоритм имеет временную сложность O(N) и использует O(1) дополнительной памяти. Например, реализация на Python 3:
74=2⋅37
2. При последовательной обработке очередного числа достаточно знать количество ранее обработанных чисел четырёх типов: всех чисел; чётных чисел; чисел, кратных 37; чисел, кратных 74.
3. Если текущее число кратно 74, его произведение с любым предыдущим числом кратно 74. Если число кратно 37, но нечётно, ему в пару нужно предыдущее чётное число. Если число чётное, но не кратно 37, ему в пару нужно предыдущее число, кратное 37. Для остальных чисел подходящих пар нет.
4. После подсчёта подходящих пар обновляются счётчики типов текущего числа. Все операции выполняются за постоянное время для каждого элемента.
5. Алгоритм имеет временную сложность O(N) и использует O(1) дополнительной памяти. Например, реализация на Python 3:
n = int(input())
all_count = 0
even_count = 0
mult37_count = 0
mult74_count = 0
answer = 0
for _ in range(n):
x = int(input())
if x % 74 == 0:
answer += all_count
elif x % 37 == 0:
answer += even_count
elif x % 2 == 0:
answer += mult37_count
all_count += 1
if x % 2 == 0:
even_count += 1
if x % 37 == 0:
mult37_count += 1
if x % 74 == 0:
mult74_count += 1
print(answer)Частые ошибки
- Перебирать все пары, получая сложность $O(N^2)$.
- Учитывать только пары «чётное число и число, кратное $37$», не обработав числа, кратные $74$.
- Добавлять текущий элемент в счётчики до подсчёта пар, из-за чего число может образовать пару само с собой.
- Хранить всю последовательность, хотя для решения достаточно нескольких счётчиков.
Источник: Открытый банк ФИПИ
Похожие задания
27Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4…Программа и описание алгоритма · 2C4C0127Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 335BFF27Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4…Программа и описание алгоритма · 37B02227На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени…Программа и описание алгоритма · 39143827Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 5D03DA27Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 5…Программа и описание алгоритма · 6A655827На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой…Программа и описание алгоритма · 6FF64727Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 7BD738
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.