Региональный этап олимпиады по экономике проводился для учеников 9–11-х классов, участвующих в общем конкурсе. Каждый участник олимпиады мог набрать от 0 до 50 баллов. Для определения призёров сначала отбираются 45% (с округлением в меньшую сторону) участников, показавших лучшие результаты.
По положению, в случае, если у последнего участника, входящего в 45%, оказывается такое же количество баллов, как и у следующих за ним в итоговой таблице, решение по данному участнику и всем участникам, имеющим с ним равное количество баллов, определяется следующим образом:
— все участники признаются призёрами, если набранные ими баллы больше половины максимально возможных;
— все участники не признаются призёрами, если набранные ими баллы не превышают половины максимально возможных.
Напишите эффективную по времени работы и по используемой памяти программу, которая по результатам олимпиады будет определять, ка- кой минимальный балл нужно было набрать, чтобы стать призёром олимпиады.
Программа должна выводить минимальный балл призёра. Гарантируется, что хотя бы одного призёра по указанным правилам определить можно.
Описание входных и выходных данных.
На вход программе сначала подаётся число участников олимпиады N.
В каждой из следующих N строк находится результат одного из участников олимпиады в следующем формате:
<�Фамилия> <�Имя> <�Класс> <�Баллы>, где <�Фамилия>—строка, состоящая не более чем из 20 символов;
<�Имя>—строка, состоящая не более чем из 15 символов;
<�Класс>—число от 9 до 11;
<�Баллы>—целое число от 0 до 60 набранных участником баллов.
<�Фамилия> и <�Имя>, <�Имя> и <�Класс>, а также <�Класс> и<�Баллы> разделены одним пробелом.
Пример входных данных:
10
Иванов Пётр 10 47
Капустин Иван 11 35
Никитин Андрей 10 44
Ломов Антон 11 47
Носов Александр 10 32
Егоров Иван 9 30
Городов Михаил 11 44
Васильев Анатолий 10 44
Зоров Денис 10 37
Петров Антон 11 48
Пример выходных данных для приведённого выше примера входных данных:
44
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N участниках олимпиады.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Программа читает все входные данные один раз, сразу подсчитывая в массиве с индексами от 0 до 50 количество участников, набравших тот или иной балл. Путём просмотра этого массива с конца (от 50 баллов) определяется число участников, заведомо попадающих в число 45 % лучших (добавление всех участников, набравших следующий балл, приводит к выходу за 45 %).
Последний балл, который набрали не менее одного участника, запоминается. Если хотя бы один из следующих участников также попадает в 45 %, то проверяется, набрал ли он и следующие, набравшие столько же баллов, более половины баллов.
В этом случае они все добавляются к числу победителей и призёров, и их балл является искомым.
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var cnt: array[0..50] of integer;
c: char; i, k, N, b, S, minb: integer;
begin
for i:=0 to 50 do cnt[i]:=0;
readln(N);
for i:=1 to N do begin
repeat
read(c);
until c=’ ’; {считана фамилия}
repeat
read(c);
until c=’ ’; {считано имя}
readln(k,b); cnt[b]:=cnt[b]+1;
end;
S:=0; b:=50;
while (S + cnt[b])*100<=N*45 do begin
S:=S+cnt[b];
if cnt[b]>0 then minb:=b;
b:=b-1
end; {определены те, кто наверняка стал призёром, и пропущены баллы, которые никто не набрал}
if (S+1)*100<=N*45 then
{если ещё хотя бы один участник попадает в 45%, то проверяется, какой балл набрал он и следующие участники}
if b>25 then minb:=b
writeln(minb)
end.