Крабоеду поручили срочно написать программу, которая в заданной последовательности неотрицательных чисел находит количество пар, произведение которых кратно 5, а номера различаются не менее, чем на 5. Известно, что значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает 10000. Напишите такую программу и спасите Крабоеда от приближающегося дедлайна.
Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов. Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования. Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности \(N\), т.е. при увеличении \(N\) в \(k\) раз время работы программы должно увеличиваться не более чем в \(k\) раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа \(N\) и не превышает 1 килобайта. Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
Максимальная оценка за правильную программу, эффективную по времени и по памяти — 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Входные данные представлены следующим образом. В первой строке задаётся число \(N\) — общее количество элементов последовательности. Гарантируется, что \(N > 5\). В каждой из следующих \(N\) строк задаётся одно неотрицательное целое число — очередной элемент последовательности.
Задание А.
Приведем одно из возможных решений задания А на языке С++:
\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N; \\ \quad int\; a[10000]; \\ \quad int\; count = 0; \\ \\ \quad for\; (int\; i = 0; i < N; i++) \\ \quad \quad cin >> a[i];\\ \\ \quad for\; (int\; i = 0; i < N; i++)\\ \quad \quad for\; (int\; j = i + 5; j < N; j++)\\ \quad \quad \quad if\; (a[i]*a[j]\%5==0) \\ \quad \quad \quad \quad count++;\\ \\ \quad cout << count;\\ \quad return\; 0;\\ \} \end{array}\]
Задание Б.
Для эффективного решения задания Б создаем буфер, в котором будем хранить первые пять элементов последовательности, а также создадим счетчики: общий и для элементов, кратных 5. Введем с клавиатуры первые 5 элементов в буфер. Затем каждый новый элемент последовательности будем проверять на кратность 5: если новый элемент кратен 5, то к общему счетчику нужно прибавить количество элементов до него, не считая пяти последних (включая считанное); если новый элемент не кратен 5, то к общему счетчику прибаляем счетчик чисел, кратных 5.
Приведем пример программы на языке С++:
\[\begin{array}{l} \#include <iostream>\\ using\; namespace\; std;\\ int\; main()\\ \{ \\ \quad int\; N;\\ \quad cin >> N;\\ \quad int\; const\; b = 5;\\ \quad int\; buf[b];\\ \\ \quad int\; x,\; count = 0, \; count\_5=0;\\ \\ \quad for\; (int\; i = 0; i < b; i++)\{\\ \quad \quad cin >> buf[i];\\ \quad \}\\ \\ \quad for\; (int\; i = b;\;i < N;\; i++)\\ \quad \{\\ \quad \quad cin >> x;\\ \quad \quad if\; (buf[0] \% 5 == 0)\\ \quad \quad \quad count\_5++;\\ \quad \quad if\; (x \% 5==0)\\ \quad \quad \quad count = count+i-b+1;\\ \quad \quad else\\ \quad \quad \quad count=count+count\_5;\\ \quad \quad for\;(int\;j=0;\;j<b-1;\;j++)\\ \quad \quad \quad buf[j]=buf[j+1];\\ \quad \quad buf[b-1]=x;\\ \quad \}\\ \\ \quad cout << count;\\ \quad return\; 0;\\ \} \end{array}\]
Ответ: _См. решение_
