Задания
Версия для печати и копирования в MS Word
Тип Д27 C4 № 16903
i

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

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

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

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

12

1

5

5

8

9

4

12

14

6

7

9

8

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

1

По­яс­не­ние. Из 12 чисел можно со­ста­вить 3 пары, удо­вле­тво­ря­ю­щие усло­вию. Это будут эле­мен­ты с ин­дек­са­ми 1 и 11, 1 и 12, 2 и 12. Для за­дан­но­го на­бо­ра чисел по­лу­ча­ем пары (1, 9), (1, 8), (5, 8). Про­из­ве­де­ния чисел в этих парах равны 9, 8, 40. На 10 де­лит­ся одно из этих про­из­ве­де­ний.

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

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

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

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

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

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

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

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

Спрятать решение

Ре­ше­ние.

Про­из­ве­де­ние двух чисел крат­но 10, если хотя бы одно из этих чисел крат­но 10, или если одно из чисел крат­но 2, а дру­гое крат­но 5.

Будем под­счи­ты­вать общее ко­ли­че­ство n1 эле­мен­тов по­сле­до­ва­тель­но­сти, ко­ли­че­ство n2 эле­мен­тов, крат­ных 2, n5  — крат­ных 5, и n10  — крат­ных 10.

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

Будем рас­смат­ри­вать каж­дое введённое число как пра­вый эле­мент воз­мож­ной пары (пер­вые 10 чисел не могут быть таким эле­мен­том). Если этот эле­мент кра­тен 10, он об­ра­зу­ет n1 под­хо­дя­щих пар, если кра­тен 5 и не кра­тен 2  — n2 под­хо­дя­щих пар, если кра­тен 2 и не кра­тен 5  — n5, в осталь­ных слу­ча­ях  — n10.

 

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

 

const s=10; {тре­бу­е­мое рас­сто­я­ние между эле­мен­та­ми}

var

    N: integer; {ко­ли­че­ство чисел}

    x: integer; {оче­ред­ное число}

    a: array[0..s-1] of integer;

    n1,n2,n5,n10: integer; {счет­чи­ки}

    k: integer; {ко­ли­че­ство пар}

    i: integer; {счётчик для ввода}

    ia: integer; {те­ку­щий ин­декс в мас­си­ве a}

begin

    readln(N);

    {ввод пер­вых s чисел}

    for i:=0 to s − 1 do readln(a[i]);

    {ввод и об­ра­бот­ка осталь­ных зна­че­ний}

    n1:=0; n2:=0; n5:=0; n10:=0;

    k := 0; ia:=0;

    for i:=s to N-1 do begin

        readln(x);

        if a[ia] mod 10 = 0 then n10 := n10 + 1;

        if a[ia] mod 5 = 0 then n5 := n5 + 1;

        if a[ia] mod 2 = 0 then n2 := n2 + 1;

        n1 := n1 +1;

        if x mod 10 = 0 then k := k + n1

        else if x mod 5 = 0 then k := k + n2

        else if x mod 2 = 0 then k := k + n5

        else k := k + n10;

        a[ia] := x;

        ia := (ia+1) mod s

    end;

    writeln(k);

end.

 

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

 

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

 

const s=10; {тре­бу­е­мое рас­сто­я­ние между эле­мен­та­ми}

var

    N: integer; {ко­ли­че­ство чисел}

    x: integer; {оче­ред­ное число}

    a: array[1..s] of integer;

    n1,n2,n5,n10: integer; {счет­чи­ки}

    k: integer; {ко­ли­че­ство пар}

    i: integer; {счётчик для ввода}

    ia: integer; {счётчик для сдви­га}

begin

    readln(N);

    {ввод пер­вых s чисел}

    for i:=1 to s do readln(a[i]);

    {ввод и об­ра­бот­ка осталь­ных зна­че­ний}

    n1:=0; n2:=0; n5:=0; n10:=0;

    k := 0; ia:=0;

    for i:=s+1 to N do begin

        readln(x);

        if a[1] mod 10 = 0 then n10 := n10 + 1;

        if a[1] mod 5 = 0 then n5 := n5 + 1;

        if a[1] mod 2 = 0 then n2 := n2 + 1;

        n1 := n1 +1;

        if x mod 10 = 0 then k := k + n1

        else if x mod 5 = 0 then k := k + n2

        else if x mod 2 = 0 then k := k + n5

        else k := k + n10;

        for ia:=1 to s-1 do a[ia]:=a[ia+1];

        a[s] := x;

    end;

    writeln(k);

end.

 

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

 

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

 

const s=10; {тре­бу­е­мое рас­сто­я­ние между эле­мен­та­ми}

var

    N: integer; {ко­ли­че­ство чисел}

    a: array [1..1000] of integer; {ис­ход­ные дан­ные}

    k: integer; {ко­ли­че­ство пар}

    i,j: integer;

begin

    readln(N);

    for i:=1 to N do readln(a[i]);

    k :=0;

    for i := 1 to N-s do begin

        for j := i+s to N do begin

            if a[i]*a[j] mod 10 = 0

                then k := k + 1;

        end;

    end;

    writeln(k);

end.

 

При­во­дим эф­фек­тив­ное ре­ше­ние Игоря Ку­да­ше­ва на Python 3.

n = int(input())

a = []

n1 = 0

n2 = 0

n5 = 0

n10 = 0

count = 0

for i in range(10):

    a.append(int(input()))

for i in range(10, n):

    x = int(input())

    if a[i % 10] % 10 == 0: n10 += 1

    if a[i % 10] % 5 == 0: n5 += 1

    if a[i % 10] % 2 == 0: n2 += 1

    n1 += 1

    if x % 10 == 0: count += n1

    if x % 5 == 0: count += n2

    if x % 2 == 0: count += n5

    count += n10

    a[i % 10] = x

print(count)

Спрятать критерии
Критерии проверки:

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы

Про­грам­ма пра­виль­но ра­бо­та­ет для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра. Ис­поль­зу­е­мая па­мять не за­ви­сит от ко­ли­че­ства про­чи­тан­ных чисел, а время ра­бо­ты про­пор­ци­о­наль­но этому ко­ли­че­ству.

До­пус­ка­ет­ся на­ли­чие в тек­сте про­грам­мы до трёх син­так­си­че­ских оши­бок од­но­го из сле­ду­ю­щих видов:

1) про­пу­щен или не­вер­но ука­зан знак пунк­ту­а­ции,

2) не­вер­но на­пи­са­но или про­пу­ще­но за­ре­зер­ви­ро­ван­ное слово языка про­грам­ми­ро­ва­ния,

3) не опи­са­на или не­вер­но опи­са­на пе­ре­мен­ная,

4) при­ме­ня­ет­ся опе­ра­ция, не­до­пу­сти­мая для со­от­вет­ству­ю­ще­го типа дан­ных.

Если одна и та же ошиб­ка встре­ча­ет­ся не­сколь­ко раз, это счи­та­ет­ся за одну ошиб­ку

4

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

Про­грам­ма в целом ра­бо­та­ет пра­виль­но для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра. Время ра­бо­ты про­пор­ци­о­наль­но ко­ли­че­ству введённых чисел, пра­виль­но ука­за­но, какие ве­ли­чи­ны

долж­ны вы­чис­лять­ся по ходу чте­ния эле­мен­тов по­сле­до­ва­тель­но­сти чисел.

Ис­поль­зу­е­мая па­мять, воз­мож­но, за­ви­сит от ко­ли­че­ства про­чи­тан­ных чисел (на­при­мер, вход­ные дан­ные за­по­ми­на­ют­ся в мас­си­ве, кон­тей­не­ре STL в C++ или дру­гой ана­ло­гич­ной струк­ту­ре дан­ных).

Ко­ли­че­ство син­так­си­че­ских оши­бок («опи­сок»), ука­зан­ных в кри­те­ри­ях на 4 балла, — не более пяти.

До­пус­ка­ет­ся на­ли­чие не более одной ошиб­ки сле­ду­ю­щих видов:

1) ошиб­ка при вводе дан­ных (не счи­ты­ва­ет­ся зна­че­ние N или не­вер­но ор­га­ни­зо­ван ввод по­сле­до­ва­тель­но­сти);

2) ошиб­ка при ини­ци­а­ли­за­ции или от­сут­ствие ини­ци­а­ли­за­ции там, где она не­об­хо­ди­ма;

3) ис­поль­зу­ет­ся не­вер­ный тип дан­ных;

4) ис­поль­зо­ва­на одна пе­ре­мен­ная (кон­стан­та) вме­сто дру­гой;

5) ис­поль­зу­ет­ся один знак опе­ра­ции вме­сто дру­го­го;

6) от­сут­ству­ет вывод от­ве­та или вы­во­дит­ся не то зна­че­ние (хотя пра­виль­ный ответ в про­грам­ме най­ден);

7) не­вер­ная ра­бо­та с мас­си­вом, в том числе выход за гра­ни­цы мас­си­ва;

8) про­пу­ще­ны или не­вер­но рас­став­ле­ны опе­ра­тор­ные скоб­ки (при ис­поль­зо­ва­нии язы­ков с опе­ра­тор­ны­ми скоб­ка­ми)

3

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

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

2

Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 2, 3 или 4 балла.

При этом про­грам­ма пред­став­ле­на и со­дер­жит как ми­ни­мум два обя­за­тель­ных эле­мен­та, воз­мож­но, ре­а­ли­зо­ван­ных с ошиб­ка­ми:

1) рас­смат­ри­ва­ют­ся толь­ко пары, на­хо­дя­щи­е­ся на рас­сто­я­нии не мень­ше за­дан­но­го в усло­вии;

2) ведётся подсчёт пар с под­хо­дя­щим про­из­ве­де­ни­ем

1
Не вы­пол­не­ны кри­те­рии, поз­во­ля­ю­щие по­ста­вить 1, 2, 3 или 4 балла0
Мак­си­маль­ный балл4
Спрятать решение · КритерииСпрятать критерии · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026