Описание входных и выходных данных. В первой строке входных данных задаётся количество чисел N (3 ≤ N ≤ 1000)

В первой строке входных данных задаётся количество чисел N (3 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.

В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 3, в которых произведение элементов кратно 13.

Пример входных данных:

6

26

2

3

5

4

13

Пример выходных данных для приведённого выше примера входных данных:

5

Пояснение. Из шести заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 26·5, 26·4, 26·13, 2·4, 2·13, 3·13. Из них на 13 делятся 5 произведений.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.

Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, – 4 балла.

Максимальная оценка за правильную программу, эффективную только по времени, –
3 балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.

 

 

Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.

Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

 

 

 

Содержание верного ответа (допускаются иные формулировки ответа, не искажающие его смысла)

Произведение двух чисел делится на 13, если хотя бы один из сомножителей делится на 13. При вводе чисел можно подсчитывать количество чисел, кратных 13, не считая 3 последних. Обозначим их n 13. Примечание для проверяющего. Сами числа, кроме 3 последних, при этом можно не хранить. Очередное считанное число будем рассматривать как возможный правый элемент искомой пары. Если очередное считанное число делится на 13, то к ответу следует прибавить количество чисел до него, не считая 3 последних (включая считанное). Если очередное считанное число на 13 не делится, то к ответу следует прибавить n 13. Чтобы построить программу, эффективную по памяти, заметим, что, поскольку при обработке очередного элемента входных данных используются значения, находящиеся на 3 элемента ранее, достаточно хранить только 3 последних элемента или информацию о них. Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)

 

Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти

const s = 3; {требуемое расстояние между элементами} var n: longint; a: array[1..s] of longint; {хранение последних s значений} a_: longint; {очередное значение} n13: longint; {количество делящихся на 13 элементов,        не считая s последних} cnt: longint; {количество искомых пар} i, j: longint; begin readln(n); {Ввод первых s чисел} for i:=1 to s do readln(a[i]); {Ввод остальных значений, подсчет искомых пар} cnt:= 0; n13:= 0; for i:= s + 1 to n do begin if a[1] mod 13 = 0 then n13:= n13 + 1; readln(a_); if a_ mod 13 = 0 then cnt:= cnt + i - s else cnt:= cnt + n13; {сдвигаем элементы вспомогательного массива влево} for j:= 1 to s - 1 do a[j]:= a[j + 1]; a[s]:= a_ {записываем текущий элемент в конец массива} end; writeln(cnt) end.

Комментарии для проверяющего 1. При таком решении хранятся только последние 3 прочитанных элемента. Таким образом, используемая память не зависит от длины последовательности. Время обработки очередного числа фиксировано, т.е. не зависит от длины последовательности. Поэтому при увеличении длины последовательности в k раз время работы программы увеличивается не более чем в k раз. Таким образом, приведённая выше программа эффективна как по времени, так и по используемой памяти. Это решение оценивается в 4 балла. В таких версиях Паскаля, как PascalABC или Delphi, тип longint может быть заменён на тип integer. В большинстве версий языков C\C++ также можно использовать тип int. Программа может быть и ещё более эффективной, если на каждом шаге не сдвигать элементы вспомогательного массива, а записывать i -й считанный элемент в элемент с индексом i mod 3 (Паскаль) или i % 3 (Python), ведя нумерацию обоих индексов с нуля. Учёту подлежит элемент с этим же индексом (именно он находится на расстоянии s от i -го и будет заменён на него). Кроме того, при нумерации индексов элементов с нуля меняется одна из формул для подсчёта. Такая программа на языке Python приведена ниже (пример 2). Все подобные программы оцениваются, исходя из максимального балла – 4 (см. критерии). Вместо последних 3 элементов можно хранить и 3 счётчика: количество делящихся на 13 среди всех считанных чисел, всех считанных чисел без последнего, всех считанных чисел без 2 последних – и также сдвигать их после очередного шага. Такая программа приведена на языке С++ (пример 3). В этом же примере вместо вспомогательного массива длиной 3 используются 3 переменные. 2. Возможно решение, основанное на описанных идеях, однако предварительно сохраняющее элементы последовательности в массив. Такое решение эффективно по времени, но неэффективно по памяти. Оно оценивается, исходя из максимального балла – 3 (см. критерии). 3. Решение, неэффективное ни по времени, ни по памяти, запоминает входную последовательность в массиве, после чего явно перебирает все возможные пары. Такое решение оценивается, исходя из максимального балла – 2 (см. критерии).

Пример 2. Программа на языке Python. Программа эффективна по времени и памяти

s = 3 a = [0]*s n = int(input()) for i in range(s): a[i] = int(input()) cnt = 0 n13 = 0 for i in range(s, n): k = i % s if a[k] % 13 == 0:    n13 = n13 + 1 a_ = int(input()) if a_ % 13 == 0:    cnt = cnt + i - s + 1 else:     cnt = cnt + n13 a[i % s] = a_ print(cnt)

 

Пример 3. Программа на языке С++. Программа эффективна по времени и памяти

#include <iostream> using namespace std; int main() { int s = 3; //требуемое расстояние между элементами int n; int n1 = 0, n2 = 0, n3 = 0; //хранение последних s счетчиков int a_; // очередное значение int cnt; // количество искомых пар cin >> n; cnt = 0; for (int i = 0; i < n; ++i) { cin >> a_; // считано очередное значение if (i >= s) {    if (a_ % 13 == 0)       cnt += i - s + 1;    else       cnt += n3; } //сдвигаем элементы счетчиков n3 = n2; n2 = n1; //обновляем счетчик кратных 13 if (a_ % 13 == 0)    n1 += 1; } cout << cnt; return 0; }

 

Указания по оцениванию	Баллы
Если в работе представлены две программы решения задачи, то каждая из них независимо оценивается по указанным ниже критериям, итоговой считается бо́льшая из двух оценок. Описание алгоритма решения без программы оценивается в 0 баллов.
Программа правильно работает для любых входных данных произвольного размера при условии исправления в ней не более трёх синтаксических ошибок из приведённого ниже списка допустимых ошибок. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству. Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано, пропущено или написано лишнее зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, не допустимая для соответствующего типа данных. Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку	4
Не выполнены условия, позволяющие поставить 4 балла. Программа работает правильно для любых входных данных произвольного размера при условии исправления в ней не более пяти синтаксических ошибок из приведённого в критериях на 4 балла списка и не более одной ошибки из приведённого ниже списка содержательных ошибок. Время работы пропорционально количеству введённых чисел. Допускается наличие не более одной содержательной (не являющейся синтаксической) ошибки следующих видов: 1) допущена ошибка при вводе данных, например не считывается значение N,или числа могут быть считаны, только если будут записаны в одной строке через пробел; 2) неверная инициализация или её отсутствие там, где она необходима; 3) используется неверный тип данных; 4) использована одна переменная (или константа) вместо другой; 5) используется один знак операции вместо другого; 6) используется одно зарезервированное слово языка программирования вместо другого; 7) неверно используется условный оператор, например else относится не к тому условию; 8) отсутствует вывод ответа, или выводится значение не той переменной; 9) выход за границу массива; 10) неверно расставлены операторные скобки. 3 балла также ставится за программу, в которой нет содержательных ошибок, но используемая память зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных)	3

 

Пример 4. Программа на языке Паскаль. Программа эффективна по времени и неэффективна по памяти

const s = 3; {требуемое расстояние между элементами} var n: longint; a: array[1..1000] of longint; n13: longint; {количество делящихся на 13 элементов, не считая s последних} cnt: longint; {количество искомых пар} i, j: longint; begin readln(n); {Ввод первых s чисел} for i:=1 to s do readln(a[i]); {Ввод остальных значений, подсчет искомых пар} cnt:= 0; n13:= 0; for i:= s + 1 to n do begin readln(a[i]); if a[i - s] mod 13 = 0 then n13:= n13 + 1; if a[i] mod 13 = 0 then cnt:= cnt + i - s else  cnt:= cnt + n13; end; writeln(cnt) end.

 

Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает верно, эффективно по времени при условии исправления не более трёх содержательных ошибок, описанных в критериях на 3 балла, и не более девяти синтаксических ошибок, указанных в критериях на 4 балла. 2 балла также ставится за корректное переборное решение, в котором все числа сохраняются в массиве (или другой аналогичной структуре), рассматриваются все возможные пары и подсчитывается количество подходящих произведений с учётом допустимого расстояния между ними. Пример фрагмента соответствующей программы на языке Паскаль: cnt:= 0; for i:= 1 to N - s do  for j:= i + s to N do if a[i] * a[j] mod 13 = 0 then    cnt:= cnt + 1; writeln(cnt) Не допускается выставление 2 баллов за реализацию переборного алгоритма, содержащего любую логическую ошибку, например ошибку, приводящую к выходу индексов за границы массива, или ошибку, когда учитываются произведения вида a[i]*a[i], или пары считаются дважды, или неверно учитывается расстояние между индексами элементов пары	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. При этом в программе должны присутствовать два обязательных элемента, возможно, реализованных с ошибками: 1) проверка делимости (в явной или неявной форме) элементов входной последовательности на заданное число; 2) проверка или учёт того, что расстояние между элементами искомой пары должно быть не меньше заданного	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл	4

 

Задание 27. Вариант 2

На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a_i и a_j, такие что i < j и a_i > a_j (первый элемент пары больше второго, i и j – порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.