Соревнования по игре «Тетрис-онлайн» проводятся по следующим правилам.
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.
Решение не рационально по памяти, т.к. содержит два огромных массива данных. На много рациональнее хранить только данные для 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.