Задание 27 ЕГЭ по информатике · 29FE86

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3: разница в индексах элементов пары должна быть 3 или более, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 23.
В первой строке входных данных задаётся количество чисел N (3≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. Программа должна вывести одно число — количество подходящих пар.
Требуется написать эффективную по времени и памяти программу. Программа считается эффективной по времени, если при увеличении N в k раз время её работы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память для хранения всех переменных не превышает 1 килобайта и не увеличивается с ростом N.
Перед текстом программы кратко опишите алгоритм решения, укажите использованный язык программирования и его версию.

1. Для пары элементов произведение кратно 23 тогда и только тогда, когда хотя бы один элемент пары кратен 23.

2. При чтении элемента с индексом i допустимыми предыдущими являются элементы с индексами не больше i−3. Поэтому перед обработкой текущего элемента в счётчик добавляется элемент, прочитанный три позиции назад.

3. Пусть count23 — количество добавленных допустимых предыдущих элементов, кратных 23, а available — общее количество добавленных допустимых элементов. Если текущий элемент кратен 23, он образует подходящую пару с каждым из available элементов. Иначе он образует подходящую пару только с count23 элементами.

4. После обработки текущего элемента его значение сохраняется в очереди из последних трёх элементов, чтобы через три шага добавить его в множество допустимых предыдущих элементов. Используется постоянное количество переменных, поэтому память не зависит от N.

5. Программа работает за O(N) по времени и за O(1) по дополнительной памяти.

6. Один из вариантов реализации на Python 3: