Задание 27 ЕГЭ по информатике · E3E824
Программа и описание алгоритмаВысокаяКЭС 3.2КЭС 3.3
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на 38.
В первой строке входных данных задаётся количество чисел N (1≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать одно число — количество пар, в которых произведение элементов кратно 38.
Пример входных данных:
4
2
6
19
57
Пример выходных данных:
4
Из четырёх заданных чисел можно составить 6 попарных произведений: 2⋅6, 2⋅19, 2⋅57, 6⋅19, 6⋅57, 19⋅57. На 38 делятся произведения 2⋅19, 2⋅57, 6⋅19, 6⋅57.
Требуется написать эффективную по времени и по памяти программу. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время её работы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память для хранения всех переменных не превышает 1 килобайта и не увеличивается с ростом N.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
В первой строке входных данных задаётся количество чисел N (1≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать одно число — количество пар, в которых произведение элементов кратно 38.
Пример входных данных:
4
2
6
19
57
Пример выходных данных:
4
Из четырёх заданных чисел можно составить 6 попарных произведений: 2⋅6, 2⋅19, 2⋅57, 6⋅19, 6⋅57, 19⋅57. На 38 делятся произведения 2⋅19, 2⋅57, 6⋅19, 6⋅57.
Требуется написать эффективную по времени и по памяти программу. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время её работы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память для хранения всех переменных не превышает 1 килобайта и не увеличивается с ростом N.
Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- Разложите число 38 на простые множители. Какие свойства должны иметь два множителя произведения?
- 38=2⋅19. Для каждого уже обработанного числа достаточно хранить, делится ли оно на 2, на 19 или на 38.
- При чтении очередного числа x посчитайте ранее прочитанные числа, с которыми оно образует произведение, кратное 38: если x кратно 38, подходят все предыдущие; если x кратно 2, нужны предыдущие числа, кратные 19; если x кратно 19, нужны предыдущие числа, кратные 2; иначе подходящих пар нет.
Решение
1. Разложим число 38 на простые множители: 38=2⋅19. Произведение двух чисел делится на 38, если в нём присутствуют множители 2 и 19.
2. Во время последовательного чтения чисел будем хранить только четыре счётчика: количество уже прочитанных чисел, количество чисел, кратных 2, количество чисел, кратных 19 и количество чисел, кратных 38. Эти счётчики занимают постоянный объём памяти.
3. Если очередное число x кратно 38, то оно образует подходящую пару с каждым предыдущим числом. Если x кратно 2, но не кратно 19, ему в пару нужны предыдущие числа, кратные 19. Если x кратно 19, но не кратно 2, ему в пару нужны предыдущие числа, кратные 2. В остальных случаях подходящих пар нет.
4. После подсчёта пар обновляем соответствующие счётчики. Каждое число обрабатывается один раз, поэтому время работы имеет порядок O(N), а дополнительная память — O(1).
5. Программа на Python 3. Для хранения ответа используется целое число, так как максимальное количество пар равно N(N−1)2.
6. ```python n = int(input()) seen = 0 count_2 = 0 count_19 = 0 count_38 = 0 answer = 0 for _ in range(n):
x = int(input()) if x % 38 == 0:
answer += seen elif x % 2 == 0:
answer += count_19 elif x % 19 == 0:
answer += count_2 seen += 1 if x % 2 == 0:
count_2 += 1 if x % 19 == 0:
count_19 += 1 if x % 38 == 0:
count_38 += 1 print(answer)
```
2. Во время последовательного чтения чисел будем хранить только четыре счётчика: количество уже прочитанных чисел, количество чисел, кратных 2, количество чисел, кратных 19 и количество чисел, кратных 38. Эти счётчики занимают постоянный объём памяти.
3. Если очередное число x кратно 38, то оно образует подходящую пару с каждым предыдущим числом. Если x кратно 2, но не кратно 19, ему в пару нужны предыдущие числа, кратные 19. Если x кратно 19, но не кратно 2, ему в пару нужны предыдущие числа, кратные 2. В остальных случаях подходящих пар нет.
4. После подсчёта пар обновляем соответствующие счётчики. Каждое число обрабатывается один раз, поэтому время работы имеет порядок O(N), а дополнительная память — O(1).
5. Программа на Python 3. Для хранения ответа используется целое число, так как максимальное количество пар равно N(N−1)2.
6. ```python n = int(input()) seen = 0 count_2 = 0 count_19 = 0 count_38 = 0 answer = 0 for _ in range(n):
x = int(input()) if x % 38 == 0:
answer += seen elif x % 2 == 0:
answer += count_19 elif x % 19 == 0:
answer += count_2 seen += 1 if x % 2 == 0:
count_2 += 1 if x % 19 == 0:
count_19 += 1 if x % 38 == 0:
count_38 += 1 print(answer)
```
Частые ошибки
- Перебирать все пары, получая сложность $O(N^2)$.
- Считать достаточным наличие делимости одного из чисел на $38$, не учитывая пары чисел, одно из которых кратно $2$, а другое — $19$.
- Обновлять счётчики до подсчёта пар, из-за чего число может образовать пару само с собой.
- Хранить всю последовательность, нарушая требование постоянного объёма памяти.
- Не учитывать числа, кратные одновременно $2$ и $19$.
Источник: Открытый банк ФИПИ
Похожие задания
27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 8F133027Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в…Программа и описание алгоритма · 902B8427Рассматриваются все пары различных элементов последовательности: порядок элементов в паре не важен.…Программа и описание алгоритма · BCE6F127На вход программе подаются строчные английские буквы. Ввод этих символов заканчивается точкой (другие…Программа и описание алгоритма · C0417927На вход программе подаются сведения о пассажирах, сдавших свой багаж в камеру хранения. В первой строке…Программа и описание алгоритма · E9F6D627Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3…Программа и описание алгоритма · ED6EB927Рассматриваются все пары различных элементов последовательности: элементы пары могут быть расположены в…Программа и описание алгоритма · F9556D27Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять рядом…Программа и описание алгоритма · FB72C9
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.