Соревнования по игре «Тетрис-онлайн» проводятся по следующим правилам.
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. Каждый участник регистрируется на сайте игры под определённым игровым именем. Имена участников не повторяются.
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.
Ниже приведён код решения на языке 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.
📚 Похожие разобранные задания по предмету:
ID 141040 • Задание №19
Среди приведенных ниже трех чисел, записанных в различных системах счисления, найдите минимальное и запишите е...
ID 33989 • Задание №24
Текстовый файл состоит не более чем из 106 символов арабских цифр (0, 1, ..., 9). Определите максимальное коли...
Официальные критерии проверки ФИПИ:
Критерии проверки:
Критерии оценивания выполнения задания | Баллы
Программа правильно работает для любых входных данных произвольного размера и находит ответ, не сохраняя информацию обо всех попытках. Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку) | 4
Программа работает верно, но размер используемой памяти зависит от количества исходных данных. Например, входные данные запоминаются в массиве или другой структуре данных, размер которой соответствует общему количеству попыток.
Допускается одна из следующих ошибок (если одна и та же ошибка повторяется несколько раз, она считается за одну).
1. Неверный ввод исходных данных
2. Неверно или неполно оформляется вывод результатов.
3. Неверно определяется порядок мест при равных результатах.
4. При выводе не учитывается, что количество участников может быть меньше К.
Допускается наличие от одной до трёх синтаксических ошибок, описанных в критериях на 4 балла | 3
Программа работает в целом верно, эффективно или нет. В реализации алгоритма допущено более 1 ошибки из числа перечисленных в предыдущем пункте или допущены другие ошибки, приводящие к неверной работе программы в отдельных случаях.
2 балла также ставится за программу, которая находит лучшие результаты, не учитывая, что некоторые из них могут принадлежать одному игроку, то есть в некоторых ситуациях может присвоить одному игроку сразу несколько мест.
Допускается наличие от одной до пяти синтаксичеких ошибок, описанных в критериях на 4 балла | 2
Программа работает в отдельных частных случаях.
Один балл также ставится, если программа написана неверно, но из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи | 1
Не выполнено ни одно из условий, позволяющих поставить 3, 2 или 1 балл | 0
Максимальный балл | 4
Критерии оценивания выполнения задания | Баллы
Программа правильно работает для любых входных данных произвольного размера и находит ответ, не сохраняя информацию обо всех попытках. Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку) | 4
Программа работает верно, но размер используемой памяти зависит от количества исходных данных. Например, входные данные запоминаются в массиве или другой структуре данных, размер которой соответствует общему количеству попыток.
Допускается одна из следующих ошибок (если одна и та же ошибка повторяется несколько раз, она считается за одну).
1. Неверный ввод исходных данных
2. Неверно или неполно оформляется вывод результатов.
3. Неверно определяется порядок мест при равных результатах.
4. При выводе не учитывается, что количество участников может быть меньше К.
Допускается наличие от одной до трёх синтаксических ошибок, описанных в критериях на 4 балла | 3
Программа работает в целом верно, эффективно или нет. В реализации алгоритма допущено более 1 ошибки из числа перечисленных в предыдущем пункте или допущены другие ошибки, приводящие к неверной работе программы в отдельных случаях.
2 балла также ставится за программу, которая находит лучшие результаты, не учитывая, что некоторые из них могут принадлежать одному игроку, то есть в некоторых ситуациях может присвоить одному игроку сразу несколько мест.
Допускается наличие от одной до пяти синтаксичеких ошибок, описанных в критериях на 4 балла | 2
Программа работает в отдельных частных случаях.
Один балл также ставится, если программа написана неверно, но из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи | 1
Не выполнено ни одно из условий, позволяющих поставить 3, 2 или 1 балл | 0
Максимальный балл | 4
🔗 Другие задания линии №19 по предмету Информатика:
ID 33084
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходя...
ID 33085
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходя...
ID 33086
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходя...
ID 33087
Два игрока, Паша и Вася, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходя...
ID 33088
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходя...