Решение:
Содержание верного ответа
(допускаются иные формулировки ответа, не искажающие его смысла)
Произведение двух чисел делится на 29, если хотя бы один из сомножителей делится на 29.
При вводе чисел можно подсчитывать количество чисел, кратных 29, не считая четырёх последних. Обозначим их n29.
Примечание для проверяющего. Сами числа, кроме четырёх последних, при этом можно не хранить.
Очередное считанное число будем рассматривать как возможный правый элемент искомой пары.
Если очередное считанное число делится на 29, то к ответу следует прибавить количество чисел до него, не считая четырёх последних (включая считанное).
Если очередное считанное число на 29 не делится, то к ответу следует прибавить n29.
Чтобы построить программу, эффективную по памяти, заметим, что, поскольку при обработке очередного элемента входных данных используются значения, находящиеся на четыре элемента ранее, достаточно
хранить только четыре последних элемента или информацию о них.
Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)
Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
const s = 4; {требуемое расстояние между элементами} var n: longint; a: array[1..s] of longint; {хранение последних s значений} a_: longint; {очередное значение} n29: longint; {количество делящихся на 29 элементов, не считая s последних} cnt: longint; {количество искомых пар} i, j: longint; begin readln(n); {Ввод первых s чисел} for i:=1 to s do readln(a[i]); {Ввод остальных значений, подсчет искомых пар} cnt := 0; n29 := 0; for i := s + 1 to n do begin if a[1] mod 29 = 0 then n29 := n29 + 1; readln(a_); if a_ mod 29 = 0 then cnt := cnt + i - s else cnt := cnt + n29; {сдвигаем элементы вспомогательного массива влево} for j := 1 to s - 1 do a[j] := a[j + 1]; a[s] := a_ {записываем текущий элемент в конец массива} end; writeln(cnt) end. |
Комментарии для проверяющего
1. При таком решении хранятся только последние 4 прочитанных элемента.
Таким образом, используемая память не зависит от длины последовательности. Время обработки очередного числа фиксировано, т.е. не зависит от длины последовательности. Поэтому при увеличении
длины последовательности в k раз время работы программы увеличивается не более чем в k раз. Таким образом, приведённая выше программа эффективна как по времени, так и по используемой памяти. Это решение оценивается в 4 балла.
В такой версии Паскаля, как PascalABC или Delphi, тип longint может быть заменён на тип integer. В большинстве версий языков C\C++ также можно использовать тип int.
Программа может быть и ещё более эффективной, если на каждом шаге не сдвигать элементы вспомогательного массива, а записывать i-й считанный элемент в элемент с индексом i mod 4 (Паскаль) или i % 4 (Python), ведя нумерацию обоих индексов с нуля. Учёту подлежит элемент с этим же индексом (именно он находится на расстоянии s от i-го и будет заменён на него). Кроме того, при нумерации индексов элементов с нуля меняется одна из формул для подсчёта.
Такая программа на языке Python приведена ниже (пример 2).
Все подобные программы оцениваются, исходя из максимального балла – 4 (см. критерии).
Вместо последних 4 элементов можно хранить и 4 счётчика: количество делящихся на 29 среди всех считанных чисел, всех считанных чисел без последнего, всех считанных чисел без 2 последних, всех считанных чисел без 3 последних, – и также сдвигать их после очередного шага. Такая программа приведена на языке С++ (пример 3). В этом же примере вместо вспомогательного массива длиной 4 используются 4 переменные.
2. Возможно решение, основанное на описанных идеях, однако предварительно сохраняющее элементы последовательности в массив. Такое решение эффективно по времени, но неэффективно по памяти. Оно
оценивается, исходя из максимального балла – 3 (см. критерии).
3. Решение, неэффективное ни по времени, ни по памяти, запоминает входную последовательность в массиве, после чего явно перебирает все возможные пары. Такое решение оценивается, исходя из максимального балла – 2 (см. критерии).
Пример 2. Программа на языке Python. Программа эффективна по времени и памяти
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
s = 4 a = [0]*s n = int(input()) for i in range(s): a[i] = int(input()) cnt = 0 n29 = 0 for i in range(s, n): k = i % s if a[k] % 29 == 0: n29 = n29 + 1 a_ = int(input()) if a_ % 29 == 0: cnt = cnt + i - s + 1 else: cnt = cnt + n29 a[i % s] = a_ print(cnt) |
или
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
|
n = int(input()) a = [] k29 = 0 k = 0 s = 0 for i in range(4): a.append(int(input())) a.append(0) for i in range(4, n): a[4] = int(input()) if a[0] % 29 == 0: k29 = k29 + 1 k = k + 1 if a[4] % 29 == 0: s = s + k else: s = s + k29 for j in range(4): a[j] = a[j + 1] print(s) |
Произведение двух чисел делится на 29, если хотя бы один из сомножителей делится на 29.
При вводе чисел можно подсчитывать количество чисел, кратных 29, не считая четырёх последних.
Обозначим их k29.
Очередное считанное число будем рассматривать как возможный правый элемент искомой пары.
Если очередное считанное число делится на 29, то к ответу следует прибавить
количество чисел до него, не считая четырёх последних (включая считанное).
Если очередное считанное число на 29 не делится, то к ответу следует прибавить k29.
Пример 3. Программа на языке С++. Программа эффективна по времени и памяти
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
|
#include <iostream> using namespace std; int main() { int s = 4; //требуемое расстояние между элементами int n; int n1 = 0, n2 = 0, n3 = 0, n4 = 0; //хранение последних s счетчиков int a_; // очередное значение int cnt; // количество искомых пар cin >> n; cnt = 0; for (int i = 0; i < n; ++i) { cin >> a_; // считано очередное значение if (i >= s) { if (a_ % 29 == 0) cnt += i - s + 1; else cnt += n4; } //сдвигаем элементы счетчиков n4 = n3; n3 = n2; n2 = n1; //обновляем счетчик кратных 29 if (a_ % 29 == 0) n1 += 1; } cout << cnt; return 0; } |
Указания по оцениванию
Если в работе представлены две программы решения задачи, то каждая из них независимо оценивается по указанным ниже критериям, итоговой считается бо́льшая из двух оценок. Описание алгоритма решения без программы оценивается в 0 баллов
Баллы — 4
Программа правильно работает для любых входных данных произвольного размера при условии исправления в ней не более трёх синтаксических ошибок из приведённого ниже списка допустимых ошибок. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально
этому количеству.
Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов:
1) пропущен или неверно указан знак пунктуации;
2) неверно написано, пропущено или написано лишнее зарезервированное слово языка программирования;
3) не описана или неверно описана переменная;
4) применяется операция, не допустимая для соответствующего типа данных.
Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку
Баллы — 3
Не выполнены условия, позволяющие поставить 4 балла.
Программа работает правильно для любых входных данных произвольного размера при условии исправления в ней не более пяти синтаксических ошибок из приведённого в критериях на 4 балла списка и не более одной ошибки из приведённого ниже списка содержательных ошибок. Время работы пропорционально количеству введённых чисел.
Допускается наличие не более одной содержательной (не являющейся синтаксической) ошибки следующих видов:
1) допущена ошибка при вводе данных, например не считывается значение N, или числа могут быть считаны,
только если будут записаны в одной строке через пробел;
2) неверная инициализация или её отсутствие там, где она необходима;
3) используется неверный тип данных;
4) использована одна переменная (или константа) вместо другой;
5) используется один знак операции вместо другого;
6) используется одно зарезервированное слово языка программирования вместо другого;
7) неверно используется условный оператор, например else относится не к тому условию;
8) отсутствует вывод ответа, или выводится значение не той переменной;
9) выход за границу массива;
10) неверно расставлены операторные скобки.
3 балла также ставится за программу, в которой нет содержательных ошибок, но используемая память зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой аналогичной структуре данных)
Пример 4. Программа на языке Паскаль. Программа эффективна по времени и неэффективна по памяти
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
const s = 4; {требуемое расстояние между элементами} var n: longint; a: array[1..1000] of longint; n29: longint; {количество делящихся на 29 элементов, не считая s последних} cnt: longint; {количество искомых пар} i, j: longint; begin readln(n); {Ввод первых s чисел} for i:=1 to s do readln(a[i]); {Ввод остальных значений, подсчет искомых пар} cnt := 0; n29 := 0; for i := s + 1 to n do begin readln(a[i]); if a[i - s] mod 29 = 0 then n29 := n29 + 1; if a[i] mod 29 = 0 then cnt := cnt + i - s else cnt := cnt + n29; end; writeln(cnt) end. |
Баллы — 2
Не выполнены условия, позволяющие поставить 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 29 = 0 then cnt := cnt + 1; writeln(cnt) |
Python
|
a = [] n = int(input()) for i in range(0, n): a.append(int(input())) d = 4 count = 0 for i in range(0, n - d): for j in range(i + d, n): if a[i] * a[j] % 29 == 0: count += 1 print(count) |
Не допускается выставление 2 баллов за реализацию переборного алгоритма, содержащего любую логическую ошибку, например ошибку, приводящую к выходу индексов за границы массива, или
ошибку, когда учитываются произведения вида a[i]*a[i], или пары считаются дважды, или неверно учитывается расстояние между индексами элементов пары
Баллы — 1
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла.
При этом в программе должны присутствовать два обязательных элемента, возможно, реализованных с ошибками:
1) проверка делимости (в явной или неявной форме) элементов входной последовательности на заданное число;
2) проверка или учёт того, что расстояние между элементами искомой пары должно быть не меньше заданного
Баллы — 0
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла