Задания
Версия для печати и копирования в MS Word
Тип Д19 C4 № 5070
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

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

все

кц

кон

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

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

До­пус­ка­ет­ся одна из сле­ду­ю­щих оши­бок (если одна и та же ошиб­ка по­вто­ря­ет­ся не­сколь­ко раз, она счи­та­ет­ся за одну).

1. Не­вер­ный ввод ис­ход­ных дан­ных

2. Не­вер­но или не­пол­но оформ­ля­ет­ся вывод ре­зуль­та­тов.

3. Не­вер­но опре­де­ля­ет­ся по­ря­док мест при рав­ных ре­зуль­та­тах.

4. При вы­во­де не учи­ты­ва­ет­ся, что ко­ли­че­ство участ­ни­ков может быть мень­ше К.

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

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

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

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

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

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

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


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