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


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

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

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

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

(количество набранных очков) фиксируется и заносится в протокол.

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

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

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

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

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

 

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

 

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

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

 

Гарантируется, что количество участников соревнований не меньше 3.

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

Программа должна вывести имена и результаты трёх лучших игроков по форме,

приведённой ниже в примере.

 

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

9

69485 Jack

95715 qwerty

95715 Alex

83647 M

197128 qwerty

95715 Jack

93289 Alex

95715 Alex

95715 M

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

данных:

1 место. qwerty (197128)

2 место. Alex (95715)

3 место. Jack (95715)

Решение.

Для каждого игрока нам необходимо знать только максимальное количество очков, которое тот смог набрать, и момент времени, в который это количество было набрано. Будем хранить для каждого игрока имя, максимальное количество очков, которое он набрал на данный момент, и время, в которое было набрано это количество. При добавлении новой записи будем пробегать по списку и искать игрока с данным именем. Если такого игрока нет, добавим его. Если есть, то сравним его предыдущий результат с новым и, если нужно, обновим. После того, как считаны все данные, три раза повторим процедуру: найдём игрока с максимальным количеством очков. Если таких несколько, выберем из них игрока и минимальным временем. Выпишем его результат. Теперь в его очки запишем -1, чтобы в следующий раз он никак не мог быть лучшим.

 

Ниже приведён код решения на языке Pascal версии 2.6.2. Эффективный по памяти и времени.

 

var a,a1,a2,a3,i,n:longint;

s,s1,s2,s3:string;

Begin

readln(n);

a1:=0;

a2:=0;

a2:=0;

s1:='';

s2:='';

s3:='';

for i:=1 to n do begin

read(a,s);

if a>a1 then begin

if s=s1 then begin a1:=a; s1:=s; end

else if s=s2 then begin a2:=a1; s2:=s1; a1:=a; s1:=s end

else begin

a3:=a2;

a2:=a1;

s3:=s2;

s2:=s1;

a1:=a;

s1:=s;

end;

end else if a>a2 then begin

if s=s2 then begin s2:=s; a2:=a; end

else if (s<>s1) then begin

a3:=a2;

s3:=s2;

a2:=a;

s2:=s;

end;

end else if a>a3 then begin

if (s<>s1) and (s<>s2) then begin

a3:=a;

s3:=s;

end;

end;

end;

writeln('1 место.',s1,' (',a1,')');

writeln('2 место.',s2,' (',a2,')');

writeln('3 место.',s3,' (',a3,')');

end.

 

 

Ниже приведён код решения на языке Pascal версии 2.6.2. Не являющегося эффективным по памяти.

 

var n, i, j, cnt, p, found, best, first, ind : longint;

s : string;

name : array [1..100000] of string;

points, num : array [1..100000] of longint;

begin

readln(n);

for i := 1 to n do

begin

read(p);

readln(s);

found := 0;

for j := 1 to cnt do

if s = name[j] then

found := j;

if found = 0 then

begin

inc(cnt);

name[cnt] := s;

points[cnt] := -1;

found := cnt;

end;

if p > points[found] then

begin

points[found] := p;

num[found] := i;

end;

end;

for i := 1 to 3 do

begin

best := -1;

for j := 1 to cnt do

if (points[j] > best) or (points[j] = best) and (num[j] < first) then

begin

best := points[j];

first := num[j];

ind := j;

end;

writeln(i, ' место.', name[ind], ' (', points[ind], ')');

points[ind] := -1;

end;

end.

Спрятать решение · · Курс 80 баллов ·
Владислав Дунаев (Пенза) 10.02.2016 22:23

Решение не рационально по памяти, т.к. содержит два огромных массива данных. На много рациональнее хранить только данные для 3 призовых мест. Например:

var a,a1,a2,a3,i,n:longint;

s,s1,s2,s3:string;

Begin

readln(n);

a1:=0;

a2:=0;

a2:=0;

s1:='';

s2:='';

s3:='';

for i:=1 to n do begin

read(a,s);

if a>a1 then begin

if s=s1 then begin a1:=a; s1:=s; end

else if s=s2 then begin a2:=a1; s2:=s1; a1:=a; s1:=s end

else begin

a3:=a2;

a2:=a1;

s3:=s2;

s2:=s1;

a1:=a;

s1:=s;

end;

end else if a>a2 then begin

if s=s2 then begin s2:=s; a2:=a; end

else if (s<>s1) then begin

a3:=a2;

s3:=s2;

a2:=a;

s2:=s;

end;

end else if a>a3 then begin

if (s<>s1) and (s<>s2) then begin

a3:=a;

s3:=s;

end;

end;

end;

writeln('1 место.',s1,' (',a1,')');

writeln('2 место.',s2,' (',a2,')');

writeln('3 место.',s3,' (',a3,')');

end.