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

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

 

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

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

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

 

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

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

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

 

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

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

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

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

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

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

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

Ре­ше­ние.

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

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

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

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

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

 

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

 

p

program N_27;

const d = 10;

var

N: integer;

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

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

x: integer;

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

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

m: integer; {мак­си­маль­ное зна­че­ние суммы квад­ра­тов}

i: integer;

begin

    readln(N);

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

    for i:=0 to d-1 do

    begin

        readln(x);

        a[i mod d] := x

    end;

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

квад­ра­тов}

    mx := 0; m := 0;

    for i := d to N-1 do

    begin

        readln(x);

        if abs(a[i mod d]) > abs(mx) then mx := abs(a[i mod d]);

        if x*x + mx*mx > m then m := x*x + mx*mx;

        a[i mod d] := abs(x)

    end;

    writeln(m)

end.

 

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

 

const d = 10;

var

N: integer;

a: array[1..10000] of integer; {хра­не­ние всех

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

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

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

m:integer; {мак­си­маль­ное зна­че­ние суммы квад­ра­тов}

i: integer;

begin

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

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

    mn := 0;

    m := 0;

    for i := d + 1 to N do

    begin

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

        if a[i]*a[i]+mn*mn > m then m := a[i]*a[i]+mn*mn

    end;

    writeln(m)

end.

 

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

 

Const d = 10;

var

N: integer;

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

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

m: integer; {мак­си­маль­ное зна­че­ние суммы квад­ра­тов}

i, j: integer;

begin

    readln(N);

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

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

    m := 0;

    for i := 1 to N-d do begin

        for j := i+d to N do begin

            if a[i]*a[i]+a[j]*a[j]>m then

                m := a[i]*a[i]+a[j]*a[j];

        end;

    end;

    writeln(m)

end.

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

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

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