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

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

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

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

В ка­че­стве ре­зуль­та­та про­грам­ма долж­на на­пе­ча­тать одно число: ко­ли­че­ство пар, в ко­то­рых про­из­ве­де­ние эле­мен­тов крат­но 10.

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

4

2

6

5

15

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

4

 

По­яс­не­ние. Из четырёх за­дан­ных чисел можно со­ста­вить 6 по­пар­ных про­из­ве­де­ний: 2 · 6, 2 · 5, 2 · 15, 6 · 5, 6 · 15, 5 · 15 (ре­зуль­та­ты: 12, 10, 30, 30, 90, 75). Из них на 10 без остат­ка де­лят­ся 4 про­из­ве­де­ния (2 · 5  =  10; 2 · 15  =  30; 6 · 5  =  30; 6 · 15  =  90).

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

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

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

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

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

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

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

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

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

Ре­ше­ние.

Про­из­ве­де­ние двух чисел де­лит­ся на 10, если вы­пол­не­но одно из сле­ду­ю­щих усло­вий (усло­вия не могут вы­пол­нять­ся од­но­вре­мен­но).

А.  Оба со­мно­жи­те­ля де­лят­ся на 10.

Б.  Один из со­мно­жи­те­лей де­лит­ся на 10, а дру­гой не де­лит­ся.

В.  Ни один из со­мно­жи­те­лей не де­лит­ся на 10, но один со­мно­жи­тель де­лит­ся на 2, а дру­гой  — на 5.

При вводе чисел можно опре­де­лять, де­лит­ся ли каж­дое из них на 10, 2 и 5, и под­счи­ты­вать сле­ду­ю­щие зна­че­ния:

1)  n10  — ко­ли­че­ство чисел, крат­ных 10;

2)  n5  — ко­ли­че­ство чисел, крат­ных 5, но не крат­ных 10;

3)  n2  — ко­ли­че­ство чисел, крат­ных 2, но не крат­ных 10.

Ко­ли­че­ство пар, удо­вле­тво­ря­ю­щих усло­вию А, можно вы­чис­лить по фор­му­ле n10 · (n10 – 1)/2.

Ко­ли­че­ство пар, удо­вле­тво­ря­ю­щих усло­вию Б, можно вы­чис­лить по фор­му­ле n10 · (N – n10).

Ко­ли­че­ство пар, удо­вле­тво­ря­ю­щих усло­вию В, можно вы­чис­лить по фор­му­ле n2 · n5.

По­это­му ис­ко­мое ко­ли­че­ство пар вы­чис­ля­ет­ся по фор­му­ле n10 · (n10 – 1)/2 + n10 · (N – n10) + n2 · n5.

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

 

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

var

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

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

     n10, n5, n2: integer;

     k10: integer; {ко­ли­че­ство тре­бу­е­мых пар}

     i: integer;

 

begin

     readln(N);

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

     for i:=1 to N do begin

         readln(a);

         if a mod 10 = 0 then

             n10 := n10 + 1

        else if a mod 5 = 0 then

             n5 := n5 + 1

         else if a mod 2 = 0 then

             n2 := n2 + 1;

    end;

    k10 := n10*(n10-1) div 2 + n10*(N-n10) + n2*n5;

    writeln(k10)

end.

 

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

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

 

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

 

var
N, count: integer;
a: array[1..1000] of integer;
i, j: integer;
begin
    readln(N);
    count := 0;
    for i := 1 to N do
        readln(a[i]);
    for i := 1 to N-1 do
        for j := i+1 to N do
            if (a[i] * a[j]) mod 10 = 0 then 
                count := count + 1;
    writeln(count);
end.
Спрятать критерии
Критерии проверки:

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

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

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

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

Аналоги к заданию № 18096: 18455 Все

Источник: ЕГЭ — 2019. До­сроч­ная волна. Ва­ри­ант 2
Спрятать решение · Прототип задания · КритерииСпрятать критерии · Помощь


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