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

Для за­дан­ной по­сле­до­ва­тель­но­сти ве­ще­ствен­ных чисел не­об­хо­ди­мо найти ми­ни­маль­ное сред­нее ариф­ме­ти­че­ское двух её эле­мен­тов, но­ме­ра ко­то­рых раз­ли­ча­ют­ся не менее чем на 9. Зна­че­ние каж­до­го эле­мен­та по­сле­до­ва­тель­но­сти не пре­вы­ша­ет 1000. Ко­ли­че­ство эле­мен­тов по­сле­до­ва­тель­но­сти не пре­вы­ша­ет 10000.

 

Вам пред­ла­га­ют­ся два за­да­ния, свя­зан­ные с этой за­да­чей: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния А и Б или одно из них по сво­е­му вы­бо­ру.

Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б. Если ре­ше­ние од­но­го из за­да­ний не пред­став­ле­но, то счи­та­ет­ся, что оцен­ка за это за­да­ние со­став­ля­ет 0 бал­лов.

За­да­ние Б яв­ля­ет­ся услож­нен­ным ва­ри­ан­том за­да­ния А, оно со­дер­жит до­пол­ни­тель­ные тре­бо­ва­ния к про­грам­ме.

 

А. На­пи­ши­те на любом языке про­грам­ми­ро­ва­ния про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, в ко­то­рой вход­ные дан­ные будут за­по­ми­нать­ся в мас­си­ве, после чего будут про­ве­ре­ны все воз­мож­ные пары эле­мен­тов.

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

Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А – 2 балла.

 

Б. На­пи­ши­те про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, ко­то­рая будет эф­фек­тив­на как по вре­ме­ни, так и по па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

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

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

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

На­по­ми­на­ем! Не за­будь­те ука­зать, к ка­ко­му за­да­нию от­но­сит­ся каж­дая из пред­став­лен­ных Вами про­грамм.

Вход­ные дан­ные пред­став­ле­ны сле­ду­ю­щим об­ра­зом. В пер­вой стро­ке задаётся число N – общее ко­ли­че­ство эле­мен­тов по­сле­до­ва­тель­но­сти.

Га­ран­ти­ру­ет­ся, что N > 9. В каж­дой из сле­ду­ю­щих N строк задаётся одно не­от­ри­ца­тель­ное целое число – оче­ред­ной эле­мент по­сле­до­ва­тель­но­сти.

 

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

10

8

10

45

55

25

35

25

14

16

9

Про­грам­ма долж­на вы­ве­сти одно число – опи­сан­ное в усло­вии сред­нее ариф­ме­ти­че­ское.

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

8.5

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

Ре­ше­ние.

За­ме­тим, что ми­ни­маль­ное сред­нее ариф­ме­ти­че­ское пар эле­мен­тов равно по­ло­ви­не ми­ни­маль­ной суммы пар эле­мен­тов. По­это­му за­да­ча сво­дит­ся к на­хож­де­нию ми­ни­маль­ной суммы эле­мен­тов на рас­сто­я­нии, не мень­шем 9, ко­то­рая при пе­ча­ти от­ве­та де­лит­ся на 2.

За­да­ние Б (ре­ше­ние для за­да­ния А при­ве­де­но ниже, см. про­грам­му 3). Для каж­до­го эле­мен­та с но­ме­ром k (ну­ме­ра­цию на­чи­на­ем с 1), на­чи­ная с k = 10, рас­смот­рим все до­пу­сти­мые по усло­ви­ям за­да­чи пары, в ко­то­рых дан­ный эле­мент яв­ля­ет­ся вто­рым.

Ми­ни­маль­ная сумма из всех этих пар будет по­лу­че­на, если пер­вым в паре будет взят ми­ни­маль­ный эле­мент среди всех, от пер­во­го и до эле­мен­та с но­ме­ром k-9. Для по­лу­че­ния эф­фек­тив­но­го по вре­ме­ни ре­ше­ния нужно по мере ввода дан­ных пом­нить ми­ни­маль­ное те­ку­щее зна­че­ние, каж­дое вновь вве­ден­ное зна­че­ние скла­ды­вать с ми­ни­му­мом, най­ден­ным на 9 эле­мен­та ранее, и вы­брать ми­ни­маль­ную из всех таких сумм. По­сколь­ку каж­дое те­ку­щее ми­ни­маль­ное зна­че­ние ис­поль­зу­ет­ся после ввода ещё 9 эле­мен­тов и после этого ста­но­вит­ся не­нуж­ным, до­ста­точ­но хра­нить толь­ко 9 по­след­них ми­ни­му­мов. Для этого можно ис­поль­зо­вать бу­фер­ный мас­сив из 9 эле­мен­тов и цик­ли­че­ски за­пол­нять его по мере ввода дан­ных. Раз­мер этого мас­си­ва не за­ви­сит от об­ще­го ко­ли­че­ства вве­ден­ных эле­мен­тов, по­это­му такое ре­ше­ние будет эф­фек­тив­ным не толь­ко по вре­ме­ни, но и по па­мя­ти.

Ниже при­во­дит­ся при­мер такой про­грам­мы

 

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

program N_27;

const d = 9;

var

N: integer;

a: array[0..d-1] of real; {буфер}

{k-е вве­ден­ное число за­пи­сы­ва­ем в ячей­ку a[k mod d]}

x: real;

mx: real; {ми­ни­маль­ное вве­ден­ное число}

{(не счи­тая 9 по­след­них)}

m: real; { ми­ни­маль­ное зна­че­ние суммы}

i: integer;

begin

    readln(N);

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

    for i:=1 to d do

    begin

        readln(x);

        a[i mod d] := x

    end;

    { Ввод осталь­ных эле­мен­тов, поиск ми­ни­маль­ной суммы}

    mx := 1001.0; m := 2001.0;

    for i := d + 1 to N do

    begin

        readln(x);

        if a[i mod d] < mx then mx := a[i mod d];

        if x + mx < m then m := x + mx;

        a[i mod d] := x

    end;

    writeln(m/2.0)

end.

 

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

 

const d = 9;

var

N: integer;

a: array[1..10000] of real; {хра­не­ние всех эле­мен­тов

по­сле­до­ва­тель­но­сти}

mn:real; {ми­ни­маль­ное вве­ден­ное число}

{не счи­тая d по­след­них}

m:real; {ми­ни­маль­ное зна­че­ние суммы}

i: integer;

begin

    readln(N);{Ввод всех эле­мен­тов по­сле­до­ва­тель­но­сти}

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

    mn := 1001.0;

    m := 2001.0;

    for i := d + 1 to N do

    begin

        if a[i-d] < mn then mn := a[i-d];

        if a[i] + mn < m then m := a[i] + mn

    end;

    writeln(m/2.0)

end.

 

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

 

Const d = 9;

var

N: integer;

a: array[1..10000] of real;

{хра­не­ние всех эле­мен­тов}

m: real; {ми­ни­маль­ное зна­че­ние суммы}

i, j: integer;

begin

    readln(N);

    {Ввод зна­че­ний эле­мен­тов}

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

    m := 2001.0;

    for i := 1 to N-d do begin

        for j := i+d to N do begin

            if a[i] + a[j] < m then m := a[i] + a[j];

        end;

    end;

    writeln(m/2.0)

end.

 

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

n = int(input())

a = []

m = 3000

mx = 3000

for i in range(9):

    a.append(float(input()))

for i in range(9, n):

    x = int(input())

    if a[i % 9] < mx: mx = a[i % 9]

    if mx + x < m: m = mx + x

    a[i % 9] = x

print(m / 2)

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

По­яс­не­ния для про­ве­ря­ю­щих.

1. За­да­ние Б яв­ля­ет­ся услож­не­ни­ем за­да­ния А. Если в ка­че­стве ре­ше­ния за­да­ния Б пред­став­ле­но ре­ше­ние за­да­ния А, то со­глас­но при­ведённым ниже кри­те­ри­ям, его оцен­ка будет такой же, как если бы это ре­ше­ние было пред­став­ле­но в ка­че­стве ре­ше­ния за­да­ния А.

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

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

 

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

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

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

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

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

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

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

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

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

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

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

в «эк­зо­ти­че­ских» си­ту­а­ци­ях. Кроме того, до­пус­ка­ет­ся на­ли­чие одной ошиб­ки, при­над­ле­жа­щей к од­но­му из сле­ду­ю­щих видов оши­бок:

1) ошиб­ка при ини­ци­а­ли­за­ции ми­ни­му­мов;

2) не­вер­но об­ра­ба­ты­ва­ет­ся си­ту­а­ция, когда один или не­сколь­ко ми­ни­и­му­мов не опре­де­ле­ны;

3) до­пу­щен выход за гра­ни­цу мас­си­ва;

4) ис­поль­зу­ет­ся знак < вме­сто <=, or вме­сто and и т. п.

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

min := 2001;

for i := 1 to N - 1 do begin

for j := i + 1 to N do begin

if ((a[i]+a[j]) mod 2 = 1) and

(a[i]+a[j] < min) then min := a[i]+a[j];

end

end;

2
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 2, 3 или 4 балла. Из опи­са­ния ал­го­рит­ма или общей струк­ту­ры про­грам­мы видно, что эк­за­ме­ну­е­мый в целом пра­виль­но пред­став­ля­ет путь ре­ше­ния за­да­чи не­за­ви­си­мо от эф­фек­тив­но­сти. При этом про­грам­ма может от­сут­ство­вать или быть пред­став­лен­ной от­дель­ны­ми фраг­мен­та­ми, без огра­ни­че­ний на ко­ли­че­ство оши­бок.1
Не вы­пол­не­ны кри­те­рии, поз­во­ля­ю­щие по­ста­вить 1, 2, 3 или 4 балла0
Мак­си­маль­ный балл4
Спрятать решение · КритерииСпрятать критерии · Помощь


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