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

Со­рев­но­ва­ния по игре «Тет­рис-он­лайн» про­во­дят­ся по сле­ду­ю­щим пра­ви­лам:

 

1.  Каж­дый участ­ник ре­ги­стри­ру­ет­ся на сайте игры под опре­делённым иг­ро­вым име­нем. Имена участ­ни­ков не по­вто­ря­ют­ся.

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

3.  Участ­ни­ки имеют право иг­рать не­сколь­ко раз. Ко­ли­че­ство по­пы­ток од­но­го участ­ни­ка не огра­ни­чи­ва­ет­ся.

4.  Окон­ча­тель­ный ре­зуль­тат участ­ни­ка опре­де­ля­ет­ся по одной, луч­шей для дан­но­го участ­ни­ка игре.

5.  Более вы­со­кое место в со­рев­но­ва­ни­ях за­ни­ма­ет участ­ник, по­ка­зав­ший луч­ший ре­зуль­тат.

6.  При ра­вен­стве ре­зуль­та­тов более вы­со­кое место за­ни­ма­ет участ­ник, рань­ше по­ка­зав­ший луч­ший ре­зуль­тат.

 

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

 

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

 

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

 

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

Пер­вая стро­ка со­дер­жит числа К  — ко­ли­че­ство име­ю­щих­ся при­зов и N  — общее ко­ли­че­ство строк про­то­ко­ла.

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

 

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

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

 

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

6 15

69485 Jack

95715 qwerty

95715 Alex

83647 M

197128 qwerty

95715 Jack

93289 Alex

95715 Alex

95715 M

32768 BilboBaggins

99824 TetrisMaster

45482 BilboBaggins

62123 BilboBaggins

77623 M

56791 Champion

 

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

1.  qwerty (197128)

2.  TetrisMaster (99824)

3.  Alex (95715)

4.  Jack (95715)

5.  M (95715)

6.  BilboBaggins (62123)

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

Ре­ше­ние.

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

 

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

 

Ниже при­во­дит­ся при­мер пра­виль­ной про­грам­мы на ал­го­рит­ми­че­ском языке. В дан­ной про­грам­ме для каж­дой стро­ки про­то­ко­ла про­смат­ри­ва­ет­ся пол­ный те­ку­щий спи­сок луч­ших ре­зуль­та­тов. До­пус­ка­ет­ся со­кра­ще­ние этого про­смот­ра за счёт до­пол­ни­тель­ных про­ве­рок.

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

алг

нач

цел К, N

ввод К, N

цел­таб суммы[1:К]

лит­таб имена[1:К]

цел сум

лит имя

цел низ, верх, место

нц для место от 1 до К

суммы[место]:= 0

имена[место]:= ""

кц

нц N раз

ввод сум, имя

верх:= 0; низ:= К

нц для место от 1 до К

если сум>суммы[место] и верх=0 то верх:= место все

если имя=имена [место] то низ:= место все

кц

если 0<верх<= низ то

нц для место от низ до верх+1 шаг −1

суммы[место]:= суммы[место −1]

имена[место]:= имена[место −1]

кц

суммы[верх]:= сум

имена[верх]:= имя

все

кц

нц для место от 1 до К

если суммы[место]>0

то вывод не, место,".",имена[место],"(",суммы[место], ")"

все

кц

кон

 

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

var 
    names: array[1..20] of string;
    sums: array[1..20] of longint;
    K, N, j, sum, place, up, down: longint;
    name: string;
begin
    readln(K, N);
    for j:=1 to 20 do names[j] := '';
    for j:=1 to 20 do sums[j] := 0;
    for j:= 1 to N do
        begin
            readln(sum, name);
            up:=0; down:= K;
            for place:= 1 to K do
                begin
                    if (sum>sums[place]) and (up=0) then up:=place;
                    if (name=names[place]) then down:= place;
                end;
            if (up>0) and (down>=up) then
                begin
                    for place:=down downto up+1 do
                        begin
                            sums[place]:= sums[place-1];
                            names[place]:= names[place-1];
                        end;
                    sums[up]:= sum;
                    names[up]:= name;
                end;
        end;
    for place:=1 to K do
        if place>0 then writeln(place,'.',names[place],' (',sums[place],')');
end.
Спрятать критерии
Критерии проверки:

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

1. Не­вер­но опре­де­ля­ет­ся номер чет­вер­ти (на­при­мер, пе­ре­пу­та­ны 2 и 4 чет­вер­ти).

2. Не­вер­но об­ра­ба­ты­ва­ют­ся точки, ле­жа­щие на осях (на­при­мер, для такой точки номер чет­вер­ти не из­ме­ня­ет­ся, и точка ока­зы­ва­ет­ся при­над­ле­жа­щей к той же чет­вер­ти, что и преды­ду­щая).

3. Не­вер­но ор­га­ни­зо­ва­но по­лу­че­ние пер­во­го зна­че­ния ми­ни­маль­но­го рас­сто­я­ния для каж­дой чет­вер­ти.

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

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

6. При вы­бо­ре чет­вер­ти для вы­во­да от­ве­та не­вер­но об­ра­ба­ты­ва­ют­ся си­ту­а­ции ра­вен­ства по­ка­за­те­лей.

7. Вы­во­дит­ся не­пол­ный или не­вер­ный ответ.

8. Дру­гие ошиб­ки, по сути ана­ло­гич­ные пе­ре­чис­лен­ным.

До­пус­ка­ет­ся на­ли­чие от одной до трёх син­так­си­че­ских оши­бок, опи­сан­ных в кри­те­ри­ях на 4 балла

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

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

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

2
Про­грам­ма ра­бо­та­ет в от­дель­ных част­ных слу­ча­ях.

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

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


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