Зарегистрироваться Войти через вк

Региональный этап олимпиады по экономике проводился для учеников 911-х классов,…

Региональный этап олимпиады по экономике проводился для учеников 911-х классов, участвующих в общем конкурсе. Каждый участник олимпиады мог набрать от 0 до 50 баллов. Для определения призёров сначала отбираются 45% (с округлением в меньшую сторону) участников, показавших лучшие результаты.

По положению, в случае, если у последнего участника, входящего в 45%, оказывается такое же количество баллов, как и у следующих за ним в итоговой таблице, решение по данному участнику и всем участникам, имеющим с ним равное количество баллов, определяется следующим образом:

- все участники признаются призёрами, если набранные ими баллы больше половины максимально возможных;

- все участники не признаются призёрами, если набранные ими баллы не превышают половины максимально возможных.

Напишите эффективную по времени работы и по используемой памяти программу, которая по результатам олимпиады будет определять, какой минимальный балл нужно было набрать, чтобы стать призёром олимпиады.

Программа должна выводить минимальный балл призёра. Гарантируется, что хотя бы одного призёра по указанным правилам определить можно.

Описание входных и выходных данных

На вход программе сначала подаётся число участников олимпиады N.

В каждой из следующих N строк находится результат одного из участников олимпиады в следующем формате:

<Фамилия> <Имя> <Класс> <Баллы>,

где <Фамилия> - строка, состоящая не более чем из 20 символов; <Имя> - строка, состоящая не более чем из 15 символов; <Класс> - число от 9 до 11;

<Баллы> - целое число от 0 до 50 набранных участником баллов. <Фамилия> и <Имя>, <Имя> и <Класс>, а также <Класс> и <Баллы> разделены одним пробелом. Пример входных данных:

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 балла.

Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Объект авторского права ООО «Легион»

Посмотреть решение

Вместе с этой задачей также решают:

Для автоматизированной системы управления движением городских пассажирских автобусов требуется написать программу, которая решает следующую задачу.

На некоторой остановке в течение…

На вход программы подаются сведения о набранных на ЕГЭ баллах учениками данной школы по трём предметам. В первой строке сообщается количество учащихся N , каждая из следующих N стр…

С клавиатуры вводится число записей N, не превышающее 1000, содержащих сведения о сетевом трафике, проходящем через компьютер, а затем сами записи в формате <время> <источник> <приёмник>, где <время> записано в вид…

С клавиатуры вводится число записей N , не превышающее 1000, содержащих сведения о сетевом трафике, проходящем через компьютер, а затем сами записи в формате <время> <источник> <приёмник>, где <время> записано в ви…