Задание 27 ЕГЭ по информатике · 6A6558
Программа и описание алгоритмаВысокаяКЭС 3.2КЭС 3.3
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 5 (разница в индексах элементов пары должна быть 5 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 17.
В первой строке входных данных задаётся количество чисел N (5≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 5, в которых произведение элементов кратно 17.
Пример входных данных:
8
34
2
3
5
4
6
7
17
Пример выходных данных для приведённого выше примера входных данных:
5
Пояснение: из восьми заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 34⋅6, 34⋅7, 34⋅17, 2⋅7, 2⋅17, 3⋅17. Из них на 17 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу. Время работы должно быть не более линейным по N, а память для хранения переменных не должна превышать 1 килобайта и не должна увеличиваться с ростом N.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
В первой строке входных данных задаётся количество чисел N (5≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 5, в которых произведение элементов кратно 17.
Пример входных данных:
8
34
2
3
5
4
6
7
17
Пример выходных данных для приведённого выше примера входных данных:
5
Пояснение: из восьми заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 34⋅6, 34⋅7, 34⋅17, 2⋅7, 2⋅17, 3⋅17. Из них на 17 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу. Время работы должно быть не более линейным по N, а память для хранения переменных не должна превышать 1 килобайта и не должна увеличиваться с ростом N.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- При каком условии произведение двух чисел делится на простое число 17?
- Для текущего элемента учитывайте только элементы, поступившие не менее чем за 5 позиций до него. Храните количество таких элементов и количество среди них чисел, кратных 17.
- Если текущий элемент кратен 17, к ответу добавляется количество всех уже допущенных элементов; иначе добавляется количество допущенных элементов, кратных 17. Для задержки в 5 позиций используйте очередь из пяти элементов.
Решение
1. Так как 17 — простое число, произведение двух чисел делится на 17 тогда и только тогда, когда хотя бы один множитель делится на 17.
17∣(aiaj)⟺17∣ai∨17∣aj
2. При обработке элемента с индексом i допустимыми являются элементы с индексами не больше i-5. Поэтому перед обработкой текущего элемента добавляем в множество допустимых элемент, прочитанный пять шагов назад.
3. Храним количество всех допустимых элементов и количество допустимых элементов, кратных 17. Если текущий элемент кратен 17, он образует подходящую пару с каждым допустимым элементом. Иначе он образует подходящую пару только с допустимыми элементами, кратными 17.
4. Для хранения пяти последних значений используется циклическая очередь размера 5. Все остальные данные обрабатываются потоково, поэтому дополнительная память не зависит от N.
5. Программа на Python 3.11:
6. from collections import deque n = int(input()) last = deque() all_old = 0 mult17_old = 0 answer = 0 for _ in range(n):
x = int(input()) if len(last) == 5:
y = last.popleft() all_old += 1 if y % 17 == 0:
mult17_old += 1 if x % 17 == 0:
answer += all_old else:
answer += mult17_old last.append(x) print(answer)
7. Каждый элемент добавляется в очередь и удаляется из неё один раз. Поэтому время работы имеет сложность O(N), а дополнительная память — O(1), поскольку очередь содержит не более пяти элементов.
T(N)=O(N),M(N)=O(1)
17∣(aiaj)⟺17∣ai∨17∣aj
2. При обработке элемента с индексом i допустимыми являются элементы с индексами не больше i-5. Поэтому перед обработкой текущего элемента добавляем в множество допустимых элемент, прочитанный пять шагов назад.
3. Храним количество всех допустимых элементов и количество допустимых элементов, кратных 17. Если текущий элемент кратен 17, он образует подходящую пару с каждым допустимым элементом. Иначе он образует подходящую пару только с допустимыми элементами, кратными 17.
4. Для хранения пяти последних значений используется циклическая очередь размера 5. Все остальные данные обрабатываются потоково, поэтому дополнительная память не зависит от N.
5. Программа на Python 3.11:
6. from collections import deque n = int(input()) last = deque() all_old = 0 mult17_old = 0 answer = 0 for _ in range(n):
x = int(input()) if len(last) == 5:
y = last.popleft() all_old += 1 if y % 17 == 0:
mult17_old += 1 if x % 17 == 0:
answer += all_old else:
answer += mult17_old last.append(x) print(answer)
7. Каждый элемент добавляется в очередь и удаляется из неё один раз. Поэтому время работы имеет сложность O(N), а дополнительная память — O(1), поскольку очередь содержит не более пяти элементов.
T(N)=O(N),M(N)=O(1)
Частые ошибки
- Учитывают элементы на расстоянии менее 5.
- Проверяют только текущий элемент на кратность 17 и забывают о предыдущем.
- Хранят всю последовательность, нарушая требование постоянной дополнительной памяти.
- Используют двойной перебор всех пар, получая сложность O(N^2).
- Добавляют элемент, находящийся ровно на расстоянии 5, слишком поздно или слишком рано.
Источник: Открытый банк ФИПИ
Похожие задания
27Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4…Программа и описание алгоритма · 37B02227На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени…Программа и описание алгоритма · 39143827Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в…Программа и описание алгоритма · 559E6927Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 5D03DA27На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой…Программа и описание алгоритма · 6FF64727Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 7BD73827Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять рядом…Программа и описание алгоритма · 8180D727Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 8F1330
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.