Региональный этап олимпиады по информатике проводился для учеников 9–11-х классов. Все ученики участвовали в общем конкурсе. Каждый участник олимпиады мог набрать от 0 до 600 баллов. По положению об олимпиаде победители определяются следующим образом.
1. Определяются все участники, набравшие наибольшее среди всех участников количество баллов. Они объявляются кандидатами в победители.
2. Если число кандидатов составляет не более 25% всех участников олимпиады, все кандидаты считаются победителями.
3. Если кандидатов в победители более 25%, то рассматривается количество баллов, набранное кандидатами в победители. Если кандидаты набрали более 300 баллов, все они объявляются победителями. Если балл, набранный кандидатами, не превышает 300 баллов, победителем не признаётся никто.
Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет определять фамилию и имя лучшего участника, не ставшего победителем олимпиады. Если следующий за баллом победителей один и тот же балл набрали несколько человек или если победителей нет, а лучших участников несколько (в этом случае они же являются искомыми), то выдаётся только число искомых участников. Гарантируется, что искомые участники (участник) имеются.
На вход программе сначала подаётся число участников олимпиады N
(N<10000).
В каждой из следующих N строк находится результат одного из участников олимпиады в следующем формате:
<Фамилия> <Имя> <класс> <баллы>,
где <Фамилия> — строка, состоящая не более чем из 20 непробельных символов; <Имя> — строка, состоящая не более чем из 15 непробельных символов; <класс> — число от 9 до 11; <баллы> — целое число от 0 до 600 набранных участником баллов. <Фамилия> и <Имя>, <Имя> и <класс>, а также <класс> и <баллы> разделены одним пробелом.
Пример входной строки:
Иванов Пётр 10 275
Программа должна выводить через пробел Фамилию и Имя искомого участника или их число. Пример выходных данных:
Кузнецов Иван
Второй вариант выходных данных:
4
Считаем данные. Для этого будем идти по каждой строке и считать количество пройденных пробелов. Если прошли ноль пробелов, то текущий символ надо отнести к имени, если один, то к фамилии, если два, то игнорируем, т. к. класс не важен, и, если три, то относим символ к количеству баллов.
При каждом считывании данных сравниваем количество баллов с максимальным, если текущий результат больше максимального, то записываем его вместо максимального, если он равен максимальному, увеличиваем счётчик в переменной, предназначенной для подсчёта участников с одинаковым максимальным количеством баллов. Если таких людей меньше 25% объявляем их победителями, если их больше 25% и они набрали более 300 баллов, также объявляем их победителями, если максимальны балл меньше 300, то выводим 0, показывая, что победителей нет.
Пример правильной и эффективной программы на языке Паскаль.
var n, i, j, spaces, max, next, cntWinner, cntNext, points : integer;
s, name, lastName, nameWinner, lastNameWinner, nameNext, lastNameNext : string;
Begin
max := 0;
cntWinner:= 0;
next:=0;
cntNext:=0;
readLn(n);
for i := 1 to n do
begin
readLn(s);
spaces := 0;
name := '';
lastName := '';
points := 0;
for j := 1 to length(s) do
if s[j] = ' ' then
inc(spaces)
else
begin
if spaces = 0 then
name:= name + s[j];
if spaces = 1 then
lastName:= lastName + s[j];
if spaces = 3 then
points:= points * 10 + ord(s[j]) - 48;
end;
if points > max then
begin
nameNext:=nameWinner;
lastNameNext:=lastNameWinner;
next:=max;
cntNext:=cntMax;
nameWinner:= name;
lastNameWinner:= lastName;
max := points;
cntWinner := 1;
end;
if points = max then cntWinner:=cntWinner+1;
else if points > next then
begin
nameNext:=name;
lastNameNext:=lastName;
next:=points;
cntNext:=1;
end;
else if points=next then cntNext:=cntNext+1;
end;
if (cntWinner * 4 > n) and (max <= 300) and (cntWinner=1) then write(nameWinner,' ',lastNameWinner);
if (cntWinner * 4 > n) and (max <= 300) and (cntWinner>1) then write(cntWinner);
if (cntWinner * 4 > n) and (max > 300) and (cntNext=1) then write(nameNext,' ',lastNameNext);
if (cntWinner * 4 > n) and (max > 300) and (cntNext>1) then write(cntNext);
if (cntWinner * 4 < n) and (cntNext = 1) then write(nameNext,' ',lastNameNext);
if (cntWinner * 4 < n) and (cntNext > 1) then write(cntNext);
End.