Задание 27 ЕГЭ по информатике · 37B022
Программа и описание алгоритмаВысокаяКЭС 3.2КЭС 3.3
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4: разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 19.
В первой строке входных данных задаётся количество чисел N (4≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 19.
Пример входных данных:
7
38
2
3
5
4
1
19
Пример выходных данных:
5
Из семи заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 38⋅4, 38⋅1, 38⋅19, 2⋅1, 2⋅19, 3⋅19. Из них на 19 делятся 5 произведений.
Требуется написать программу, эффективную по времени и памяти. Время работы при увеличении N в k раз должно увеличиваться не более чем в k раз. Память для хранения всех переменных программы не должна превышать 1 килобайта и не должна увеличиваться с ростом N. Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
В первой строке входных данных задаётся количество чисел N (4≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 19.
Пример входных данных:
7
38
2
3
5
4
1
19
Пример выходных данных:
5
Из семи заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 38⋅4, 38⋅1, 38⋅19, 2⋅1, 2⋅19, 3⋅19. Из них на 19 делятся 5 произведений.
Требуется написать программу, эффективную по времени и памяти. Время работы при увеличении N в k раз должно увеличиваться не более чем в k раз. Память для хранения всех переменных программы не должна превышать 1 килобайта и не должна увеличиваться с ростом N. Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Развёрнутый ответ: проверяется по критериям ФИПИ.
Подсказки (3)
- От чего зависит делимость произведения двух чисел на 19?
- Произведение делится на 19, если хотя бы один из множителей делится на 19. Для каждого текущего элемента учитывайте только элементы, расположенные не ближе чем на 4 позиции слева.
- Храните количество чисел, кратных 19, среди уже прочитанных элементов, исключая последние три. При чтении очередного числа увеличивайте ответ на это количество, затем добавляйте число, которое стало достаточно удалённым: через очередь или переменные для задержки на 3 позиции.
Решение
1. Для двух положительных чисел произведение кратно 19, если хотя бы одно из них кратно 19, поскольку 19 — простое число.
2. При обработке элемента с индексом i допустимыми являются элементы с индексами не больше i−4. Поэтому достаточно знать количество чисел, кратных 19, среди всех уже обработанных элементов, кроме трёх последних.
3. Используем три переменные задержки для последних трёх чисел. Перед обработкой числа с индексом i в счётчик удалённых от текущего элементов добавляется информация о числе с индексом i−3; после этого в ответ добавляется количество ранее учтённых чисел, кратных 19.
4. После обработки текущего числа сдвигаем задержку. Все переменные имеют постоянный размер, поэтому память не зависит от N, а каждый элемент обрабатывается один раз.
5. Пример программы на Python 3.11:
6. Код использует три логические переменные для хранения признаков делимости чисел, отстающих от текущего на 1, 2 и 3 позиции.
count=0;answer=0
7. Для каждого нового числа сначала учитываются подходящие предыдущие числа, затем выполняется сдвиг задержек.
answer+=count,count+=d3
2. При обработке элемента с индексом i допустимыми являются элементы с индексами не больше i−4. Поэтому достаточно знать количество чисел, кратных 19, среди всех уже обработанных элементов, кроме трёх последних.
3. Используем три переменные задержки для последних трёх чисел. Перед обработкой числа с индексом i в счётчик удалённых от текущего элементов добавляется информация о числе с индексом i−3; после этого в ответ добавляется количество ранее учтённых чисел, кратных 19.
4. После обработки текущего числа сдвигаем задержку. Все переменные имеют постоянный размер, поэтому память не зависит от N, а каждый элемент обрабатывается один раз.
5. Пример программы на Python 3.11:
6. Код использует три логические переменные для хранения признаков делимости чисел, отстающих от текущего на 1, 2 и 3 позиции.
count=0;answer=0
7. Для каждого нового числа сначала учитываются подходящие предыдущие числа, затем выполняется сдвиг задержек.
answer+=count,count+=d3
Частые ошибки
- Учитывать пары с расстоянием 1, 2 или 3.
- Считать все пары двойным циклом, получая сложность $O(N^2)$.
- Хранить всю последовательность, нарушая требование постоянного объёма памяти.
- Проверять только остаток текущего числа и забывать о ранее встреченных числах, кратных 19.
- Неправильно обновлять задержку и добавлять в счётчик число, которое находится на расстоянии менее 4 позиций.
Источник: Открытый банк ФИПИ
Похожие задания
27Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 2931D927Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3…Программа и описание алгоритма · 29FE8627Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4…Программа и описание алгоритма · 2C4C0127Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 335BFF27На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени…Программа и описание алгоритма · 39143827Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в…Программа и описание алгоритма · 559E6927Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности…Программа и описание алгоритма · 5D03DA27Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 5…Программа и описание алгоритма · 6A6558
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.