Муниципальный этап олимпиады по информатике проводился для учеников 7–11-х классов. Все ученики участвовали в общем конкурсе. Каждый участник олимпиады мог набрать от 0 до 400 баллов. По положению об олимпиаде победителем признаётся участник, набравший наибольшее количество баллов, при условии, что им набрано больше половины возможных баллов. Победителей может быть несколько, если это количество баллов наберут несколько человек; а может и не быть совсем, если никто не наберёт больше половины.
Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет определять фамилию и имя лучшего участника, не ставшего победителем олимпиады. Если следующий за баллом победителей один и тот же балл набрали несколько человек или если победителей нет, а лучших участников несколько (в этом случае они же являются искомыми), то должно выдаваться только число искомых участников. Гарантируется, что искомые участники (участник) имеются. На вход программе сначала подаётся число участников олимпиады N (N<10000).
В каждой из следующих N строк находится результат одного из участников олимпиады в следующем формате:
<Фамилия> <Имя> <класс> <баллы>,
где <Фамилия> — строка, состоящая не более чем из 20 непробельных символов; <Имя> — строка, состоящая не более чем из 15 непробельных символов; <класс> — число от 7 до 11; <баллы> — целое число от 0 до 400 набранных участником баллов. <Фамилия> и <Имя>, <Имя> и <класс>, а также <класс> и <баллы> разделены одним пробелом.
Пример входной строки:
Иванов Пётр 10 275
Программа должна выводить через пробел Фамилию и Имя искомого участника или их число. Пример выходных данных:
Кузнецов Иван
Второй вариант выходных данных:
4
Считываем данные. Для этого будем идти по каждой строке и считать количество пройденных пробелов. Если прошли ноль пробелов, то текущий символ надо отнести к имени, если один, то к фамилии, если два, то игнорируем, т. к. класс не важен, и, если три, то относим символ к количеству баллов.
При каждом считывании данных сравниваем количество баллов с максимальным, если оно меньше или равно 200, то это то количество баллов, которое имеется у искомых школьников. Иначе, ищем тот результат, который меньше максимального, но при этом наиболее близок к нему. Найдя такой результат сохраним имя и фамилию школьника в специально отведённых для этого переменных. Если же такой результат уже есть будем увеличивать счёт в переменной, предназначенной для подсчёта участников с одинаковым количеством баллов.
Пример правильной и эффективной программы на языке Паскаль:
var n, i, j, spaces, max, next, cnt, points: integer;
s, name, lastName, nameNext, lastNameNext: string;
var n, i, j, spaces, max, next, cnt, points, cntMax,: integer;
s, name, lastName, nameNext, lastNameNext, nameMax, lastNameMax: string;
Begin
max:= 0;
cnt:=1;
for i := 1 to n do
begin
readLn(s);
spaces := 0;
name := '';
lastName := '';
points := 0;
for j := 1 to length(s) do
begin
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
next:=max;
nameNext:=nameMax;
lastNameNext:=lastNameMax;
cnt:=cntMax;
max := points;
nameMax:= name;
lastNameMax:= lastName;
cntMax:=1
if max < 201 then
begin
next:=max;
nameNext:= name;
lastNameNext:= lastName;
cnt:=1
end
else
if (points <> max) and (points > next) then
begin
next:=points;
nameNext:= name;
lastNameNext:= lastName;
cnt:=1;
end
else if points = next then cnt:=cnt+1
else if points = max the cntMax:=cntMax+1;
end;
end;
if cnt = 1 then
write(nameNext, ' ', lastNameNext)
else
write(cnt);
End.