Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше 6 (разница в индексах элементов должна быть 6 или более).... | Яндекс.Репетитор

Задание#T29771

Дана последовательность целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше (разница в индексах элементов должна быть или более). Необходимо определить количество пар, сумма чисел в которых кратна

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел

В каждой из последующих N строк записано одно натуральное число, не превышающее

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

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

Пояснение. Из восьми чисел можно составить три пары, удовлетворяющие условию. Это будут элементы с индексами и

и Для заданного набора чисел получаем пары

Суммы чисел в этих парах равны

Одна из этих сумм кратна

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

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

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

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

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

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

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

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

Показать разбор

Содержание верного ответа

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

Сумма двух чисел кратна если сумма остатков от деления этих чисел на равна

Будем хранить количество чисел, дающих при делении на остатки

и без учёта шести последних элементов последовательности. Для этого понадобится хранить последние шесть элементов. Остальные элементы последовательности можно не хранить, это обеспечивает эффективность по памяти. Для хранения шести элементов можно использовать циклический массив, как показано в решении 1.

Будем рассматривать каждое введённое число как правый элемент возможной пары (первые шесть чисел не могут быть таким элементом) и в зависимости от остатка при его делении на определять количество подходящих пар и прибавлять его к общей сумме.

Решение 1. Правильная и эффективная программа на языке Паскаль (циклический массив, счётчики в отдельном массиве)

const d=6; {требуемое расстояние между элементами}
var 
    N: integer;     {количество чисел}
    x: integer;     {очередное число}
    a: array[0..d-1] of integer;
    k: array[0..2] of integer; {количество по остаткам}
    s: integer;     {количество подходящих пар}
    i: integer;     {счётчик для ввода}
    ia: integer;    {текущий индекс в массиве a}
begin
    readln(N);
    {ввод первых d чисел}
    for i:=0 to d-1 do readln(a[i]);
    {ввод и обработка остальных значений}
    for i:=0 to 2 do k[i]:=0;
    ia:=0; s:=0;
    for i:=d to N-1 do begin
        readln(x);
        k[a[ia] mod 3] := k[a[ia] mod 3] + 1;
        s := s + k[(3 – x mod 3) mod 3];
        a[ia] := x;
        ia := (ia+1) mod d
    end;
    writeln(s)
end.

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

Для хранения счётчиков по остаткам можно вместо массива из трёх элементов использовать три отдельные переменные. Это делает программу чуть более громоздкой, но не влияет на эффективность.

Ниже приводится пример программы, в которой использованы эти методы.

Решение 2. Правильная и эффективная программа на языке Паскаль (сдвиг массива, счётчики в отдельных переменных)

const d=6; {требуемое расстояние между элементами}
var 
    N: integer;     {количество чисел}
    x: integer;     {очередное число}
    a: array[1..d] of integer;
    k0, k1, k2: integer; {количество по остаткам}
    s: integer;     {количество подходящих пар}
    i: integer;     {счётчик для ввода}
    ia: integer;    {счётчик для сдвига}
begin
    readln(N);
    {ввод первых d чисел}
    for i:=1 to d do readln(a[i]);
    {ввод и обработка остальных значений}
    k0 := 0; k1 :=0; k2:=0;
    s:=0;
    for i:=d+1 to N do begin
        readln(x);
        if a[1] mod 3 = 0 then k0 := k0 + 1;
        if a[1] mod 3 = 1 then k1 := k1 + 1;
        if a[1] mod 3 = 2 then k2 := k2 + 1;
        if x mod 3 = 0 then s := s + k0;
        if x mod 3 = 1 then s := s + k2;
        if x mod 3 = 2 then s := s + k1;
        for ia:=1 to s-1 do a[ia]:=a[ia+1];
        a[s] := x;
    end;
    writeln(s)
end.

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

Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC).

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

const d=6; {требуемое расстояние между элементами}
var 
    N: integer;     {количество чисел}
    a: array [1..1000] of integer;  {исходные данные}
    s: integer;     {количество подходящих пар}
    i,j: integer;

begin
    readln(N);
    for i:=1 to N do readln(a[i]);
    s :=0;
    for i := 1 to N-d do begin
        for j := i+d to N do begin
            if (a[i] + a[j]) mod 3 = 0
              then s := s +1
        end
    end;
    writeln(s)
end.

Указания по оцениванию

Если в работе представлены две программы решения задачи, то каждая из них независимо оценивается по указанным ниже критериям, итоговой считается бόльшая из двух оценок. Описание алгоритма решения без программы оценивается в баллов.

Критерии оценки

4 баллаПрограмма правильно работает для любых входных данных произвольного размера. Используемая память не зависит от количества прочитанных чисел, а время работы пропорционально этому количеству.
Допускается наличие в тексте программы до трёх синтаксических ошибок одного из следующих видов:
1. пропущен или неверно указан знак пунктуации;
2. неверно написано, пропущено или написано лишнее зарезервированное слово языка программирования;
3. не описана или неверно описана переменная;
4. применяется операция, недопустимая для соответствующего типа данных.
Если одна и та же ошибка встречается несколько раз, это считается за одну ошибку

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

2 баллаНе выполнены условия, позволяющие поставить или балла, при этом программа работает в целом верно и эффективно по времени. Допускается наличие до трёх содержательных ошибок, описанных в критериях на балла, и до девяти синтаксических ошибок, описанных в критериях на балла.
ИЛИ Программа работает в целом верно и эффективно по времени, но в ней есть не подходящие под перечень из критериев на балла ошибки, которые в некоторых особых случаях приводят к неверным результатам.
ИЛИ Представлено корректное переборное решение, в котором все исходные данные сохраняются в массиве (или другой аналогичной структуре) и рассматриваются все возможные пары. При этом не допускаются содержательные логические ошибки, например, выход индексов за границы массива, неверный учёт расстояния между элементами и т. д.

1 баллНе выполнены условия, позволяющие поставить

или балла.
При этом программа представлена и содержит как минимум два обязательных элемента, возможно, реализованных с ошибками:
1. рассматриваются только пары, находящиеся на расстоянии не меньше заданного в условии;
2. ведётся подсчёт пар с подходящей суммой

0 балловНе выполнены условия, позволяющие поставить

или балла

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 1 тыс. раз. С ним справились 68% пользователей.

Это задание в разделах:

Умение создавать собственные программы (20–40 строк) для анализа числовых последовательностей

Это задание в тестах:

Тренировочный вариант ЕГЭ по информатике №43

Задание#T29771

Описание входных и выходных данных

Это задание в разделах:

Это задание в тестах:

Рекомендованные задания