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

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

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

Ре­ше­ние 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.

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

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

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

Ре­ше­ние 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 d-1 do a[ia]:=a[ia+1];

        a[d] := x;

    end;

    writeln(s)

end.

Воз­мож­но также «ло­бо­вое» ре­ше­ние: за­пи­шем все ис­ход­ные числа в мас­сив, пе­ре­берём все воз­мож­ные пары и под­счи­та­ем ко­ли­че­ство под­хо­дя­щих. Такое ре­ше­ние не яв­ля­ет­ся эф­фек­тив­ным ни по па­мя­ти (тре­бу­е­мая па­мять за­ви­сит от раз­ме­ра ис­ход­ных дан­ных), ни по вре­ме­ни (ко­ли­че­ство воз­мож­ных пар, а зна­чит, ко­ли­че­ство дей­ствий и время счёта с ро­стом ко­ли­че­ства ис­ход­ных эле­мен­тов растёт квад­ра­тич­но). Такая про­грам­ма оце­ни­ва­ет­ся не выше 2 бал­лов Ниже при­ве­де­на ре­а­ли­зу­ю­щая опи­сан­ный выше ал­го­ритм про­грам­ма на языке Пас­каль (ис­поль­зо­ва­на вер­сия 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.