СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


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

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

 

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.