Решение: Пары чисел, кратные 19
На вход программы поступает последовательность из $N$ целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4: разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 19.
В первой строке входных данных задаётся количество чисел $N$ ($4 \le N \le 1000$). В каждой из последующих $N$ строк записано одно целое положительное число, не превышающее 10000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 19.
Пример входных данных:
7
38
2
3
5
4
1
19
Пример выходных данных:
5
Из семи заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: $38 \cdot 4$, $38 \cdot 1$, $38 \cdot 19$, $2 \cdot 1$, $2 \cdot 19$, $3 \cdot 19$. Из них на 19 делятся 5 произведений.
Требуется написать программу, эффективную по времени и памяти. Время работы при увеличении $N$ в $k$ раз должно увеличиваться не более чем в $k$ раз. Память для хранения всех переменных программы не должна превышать 1 килобайта и не должна увеличиваться с ростом $N$. Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.
Решение по шагам
7 шаговДля двух положительных чисел произведение кратно 19, если хотя бы одно из них кратно 19, поскольку 19 — простое число.
При обработке элемента с индексом $i$ допустимыми являются элементы с индексами не больше $i-4$. Поэтому достаточно знать количество чисел, кратных 19, среди всех уже обработанных элементов, кроме трёх последних.
Используем три переменные задержки для последних трёх чисел. Перед обработкой числа с индексом $i$ в счётчик удалённых от текущего элементов добавляется информация о числе с индексом $i-3$; после этого в ответ добавляется количество ранее учтённых чисел, кратных 19.
После обработки текущего числа сдвигаем задержку. Все переменные имеют постоянный размер, поэтому память не зависит от $N$, а каждый элемент обрабатывается один раз.
Пример программы на Python 3.11:
Код использует три логические переменные для хранения признаков делимости чисел, отстающих от текущего на 1, 2 и 3 позиции.
$$count = 0; answer = 0$$Для каждого нового числа сначала учитываются подходящие предыдущие числа, затем выполняется сдвиг задержек.
$$answer \mathrel{+}= count,\quad count \mathrel{+}= d_3$$Алгоритм работает за $O(N)$ времени и использует $O(1)$ дополнительной памяти.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывать пары с расстоянием 1, 2 или 3.
Считать все пары двойным циклом, получая сложность $O(N^2)$.
Хранить всю последовательность, нарушая требование постоянного объёма памяти.
Проверять только остаток текущего числа и забывать о ранее встреченных числах, кратных 19.
Неправильно обновлять задержку и добавлять в счётчик число, которое находится на расстоянии менее 4 позиций.