В этом листке мы попытаемся вспомнить всё, о чём многие уже забыли: как работать со строками, списками, словарями, а так же чем именно пользоваться в разных ситуациях.
Все задачи в этом листке навеяны задачами С4 из ЕГЭ по информатике предыдущих лет.
Отличительной особенностью ЕГЭ зачастую являются тонкие формулировки с большим количеством случаев,
отсутствием внятных примеров, невозможностью автоматически протестировать своё решение,
а также необходимостью написать решение, эффективное по времени работы и по памяти.
(С 2021 «эффективное» перестало быть актуальным).
Об этом последнем требовании немного подробнее.
В каждой из этих задач нужно написать решение, которое с точностью до константы асимптотически является самым оптимальным по времени работы и по памяти.
Это означает, что если самое оптимальное решение требует времени порядка Cn, где n — длина входа,
то и сдаваемое решение должно обладать такой же асимптотикой. Если самое оптимальное решение требует O(1) памяти (то есть существует константа C такая, что на любом входе программе требуется не больше, чем C памяти), то и ваше решение должно обладать этим свойством.
Обычно это означает, что данные нужно считывать посимвольно или построчно, и в памяти при этом нельзя хранить все входные данные.
Для того, чтобы ограничения на вход не подсказывали требуемую асимптотику, несущественные ограничения указываться не будут.
При этом везде выполняются следующие ограничения (которые позволят писать программу на С++):
Любое текстовое слово, фамилия, имя и т.п. имеют длину не более 20, если иного не указано явно;
Любое целое число, в том числе целочисленный ответ на любую задачу, не превосходит по модулю 2 000 000 000;
Любое действительное число, в том числе действительный ответ на любую задачу, не превосходит по модулю 2 000 000 000 и не требует точности более 5 знаков после запятой;
Все задачи в этом листке идут в случайном порядке, они даже были специально перемешаны при помощи random.shuffle.
PS.
Для эмуляции ЕГЭ до окончания сдачи листка решения будут проверяться только на тестах из условия.
Окончательная проверка с простановкой баллов будет выполнена в дату окончания сдачи.
Тесты разбиты на четыре группы: тесты из условия, нормальные тесты, тест на время работы, тест на потребляемую память.
Каждая программа получает следующую оценку:
(доля пройденных тестов) * 2 + (1 если пройден тест на время работы, иначе 0) + (1 если пройден тест на потребляемую память, иначе 0)
A: Сигма 2015
В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли.
По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015».
Временем, в течение которого происходит передача, можно пренебречь.
Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут.
Если получить такое произведение не удаётся, ответ считается равным –1.
Каждая строка входных данных содержит одно положительное целое число – очередное показание прибора.
Общее количество строк не меньше 7.
Программа должна вывести одно число – описанное в условии произведение либо –1, если получить такое произведение не удаётся.
12
45
5
3
17
23
21
20
19
18
17
54
IDE
B: Архиватор в base64
По стандарту файлы-вложения в электронной почте конвертируются в base64.
Это означает, что бинарный файл записывается в текстовом виде, используя следующий алфавит из 64 печатных символов:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/.
Например, файл, содержащий текст «Man» будет закодирован в «TWFu»,
а бинарная строка из трёх нулей (x'000000') превратится в «AAAA».
Из-за этого размер письма увеличивается примерно на треть.
Чтобы сократить размер письма, необходимо написать простой архиватор, сокращающий куски из одного и того же повторяющегося символа.
А именно каждая последовательность из 4-67 повторяющихся символов заменяется на конструкцию =sn, где s — повторяющийся символ, а n — количество повторов минуc четыре, записанное в 64-ричной системе счисления (описанной выше).
Соревнования по игре «Тетрис-онлайн» проводятся по следующим правилам.
Каждый участник регистрируется на сайте игры под определённым игровым
именем. Имена участников не повторяются.
Чемпионат проводится в течение определённого времени. В любой момент
этого времени любой зарегистрированный участник может зайти на сайт
чемпионата и начать зачётную игру. По окончании игры её результат
(количество набранных очков) фиксируется и заносится в протокол.
Участники имеют право играть несколько раз. Количество попыток одного
участника не ограничивается.
Окончательный результат участника определяется по одной игре, лучшей для
данного участника.
Более высокое место в соревнованиях занимает участник, показавший лучший
результат.
При равенстве результатов более высокое место занимает участник, раньше
показавший лучший результат.
В ходе соревнований заполняется протокол, каждая строка которого
описывает одну игру и содержит результат участника и его игровое имя.
Протокол формируется в реальном времени по ходу проведения чемпионата,
поэтому строки в нём расположены в порядке проведения игр: чем раньше
встречается строка в протоколе, тем раньше закончилась соответствующая
этой строке игра.
Напишите программу, которая по
данным протокола определяет победителя и призёров. Гарантируется, что в
чемпионате участвует не менее трёх игроков.
Описание входных данных.
Первая строка содержит число N — общее количество строк протокола. Каждая
из следующих N строк содержит записанные через пробел результат
участника (целое неотрицательное число) и
игровое имя (имя не может содержать пробелов). Строки исходных данных
соответствуют строкам протокола и расположены в том же порядке, что и в
протоколе.
Гарантируется, что количество участников соревнований не меньше 3.
Описание выходных данных.
Программа должна вывести имена и результаты трёх лучших игроков по
форме, приведённой ниже в примере.
9
69485 Jack
95715 qwerty
95715 Alex
83647 М
197128 qwerty
95715 Jack
93289 Alex
95715 Alex
95710 M
1 место. qwerty (197128)
2 место. Alex (95715)
3 место. Jack (95715)
D: Неравномерный двоичный код
По каналу связи передастся последовательность
слов в алфавите {А, Е, Р}. Длина каждого слова не превосходит
10 букв, слова могут не быть осмысленными словами русского
языка. Каждое слово передается в виде целого числа, полученного
следующим образом.
1) Сначала слово кодируется с помощью неравномерною двоичного
кода с кодовыми словами: Е – 0; Р – 10; А – 11.
2) К полученной двоичной последовательности справа приписывается цифра 1.
3) Полученная двоичная цепочка переворачивается, то есть,
из цепочки 01010111 получается 11101010.
4) Искомое число N вычисляется в результате перевода двоичной
цепочки, полученной на предыдущем шаге, в десятичную систему.
Например, символьная последовательность ААЕЕР будет преобразована
в 11110010, затем (добавляем единицу в конец) – в 111100101, а
затем – в число: 1 + 2 + 4 + 8 + 64 + 256 = 335.
Отметим, что 335 = 101001111_2.
Напишите программу, которая, получив на вход натуральное число,
декодирует переданное сообщение и определяет, сколько раз в
исходном слове встречаются гласные буквы.
5483
AEPAEPP
4
Примечание. В этом примере: исходное слово: АЕРАЕРР.
Кодовая двоичная последовательность: 110101101010,
после добавления 1 справа получим: 1101011010101.
IDE
E: Книги в библиотеке
В одной из библиотек введена электронная система учета книг.
По результатам работы за 2014 год получен файл.
В каждой строчке файла указаны даты выдачи книги на руки, дата возвращения книги, её наименование и идентификационный номер.
Даты указаны в формате ДД.ММ.ГГГГ.
Записи упорядочены по названию книги.
Необходимо определить в какие периоды на руках населения было больше всего книг.
Первой строчкой на вход подаётся число N — количество записей.
Первой строчкой вывода должно быть максимальное число книг, которые были одновременно выданы в течение года.
Далее должны быть перечислены периоды времени, когда было выдано данное максимальное количество книг,
в порядке увеличения даты.
4
28.02.2014 15.04.2014 Война и мир №895781789
11.01.2014 03.02.2014 Капитанская дочка №5123112
13.04.2014 29.04.2014 Преступление и наказание №124123
23.01.2014 23.01.2014 Преступление и наказание №509001
2
23.01.2014 23.01.2014
13.04.2014 15.04.2014
F: Полупроходной балл
Для поступления в вуз абитуриент должен предъявить результаты трех экзаменов в виде ЕГЭ, каждый из них оценивается целым числом от 0 до 100 баллов. При этом абитуриенты, набравшие менее 40 баллов (неудовлетворительную оценку) по любому экзамену из конкурса выбывают. Остальные абитуриенты участвуют в конкурсе по сумме баллов за три экзамена.
В конкурсе участвует N человек, при этом количество мест равно K. Определите полупроходной балл, то есть такое значение балла, что количество абитуриентов, набравших балл выше полупроходного, меньше K, а количество абитурентов, набравших балл выше или равный полупроходному, больше K.
Программа получает на вход количество мест K. Далее идут строки с информацией об абитуриентах, каждая из которых состоит из имени (текстовая строка содержащая произвольное число пробелов) и трех чисел от 0 до 100, разделенных пробелами.
Программа должна вывести значение полупроходного балла, если полупроходного балла не существует, программа должна вывести одно число 0.
5
Иванов Сергей 70 70 70
Сергеев Петр 100 100 0
Петров Василий 70 60 70
Васильев Андрей 70 60 70
Андреев Денис 100 30 100
Денисов Роман 50 50 50
Романов Иван 60 70 70
Ким Чен Ир 50 50 50
Ким Ир Сен 40 40 40
150
1
Иванов Сергей 50 50 50
Сергеев Петр 100 100 100
Ким Ир Сен 100 0 100
0
IDE
G: Контрольное значение
По каналу связи передаётся последовательность положительных целых чисел. Количество чисел известно, но может быть очень велико.
Необходимо вычислить контрольное значение последовательности — наибольшее число R, удовлетворяющее следующим условиям:
1) R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2) R делится на 21.
Если такого числа R нет, то контрольное значение полагается равным 0.
Напишите программу, которая будет вычислять контрольное значение.
Программа получает набор натуральных чисел, по одному в строке, и должна вывести исходное контрольное значение.
70
21
997
7
9
300
21000
IDE
H: Числа прописью
Вам необходимо написать программу распознавания чисел, записанных
прописью. На вход программе подается значение N — количество записей,
которые необходимо обработать. Следующие N строк содержат записанные
словами числа. Каждое число записано по-русски, маленькими буквами, без
ошибок. Если число состоит из нескольких слов, между словами находится
ровно один пробел, лишних пробелов в начале и в конце строк нет.
Все числа не превосходят миллиарда.
5
двадцать восемь
два миллиона
четырнадцать
сто двадцать три
тысяча девятьсот восемьдесят четыре
28
2000000
14
123
1984
I: Самый старший
Имеется список людей с указанием их фамилии, имени и даты рождения.
Напишите программу, которая будет определять самого
старшего человека из этого списка и выводить его фамилию и имя, а если
имеется несколько самых старших людей с одинаковой датой рождения, то
определять их количество.
На вход программе в первой строке подается количество людей в списке
N. В каждой из последующих N строк находится информация в следующем
формате:
<Фамилия> <Имя> <Дата рождения>
где <Фамилия> – строка, состоящая не более, чем из 20 символов без
пробелов, <Имя> – строка, состоящая не более, чем из 20 символов без
пробелов, <Дата рождения> – строка, имеющая вид ДД.ММ.ГГГГ, где ДД –
двузначное число от 01 до 31, ММ – двузначное число от 01 до 12, ГГГГ
– четырехзначное число от 1800 до 2100.
Программа должна вывести фамилию и имя самого старшего человека в
списке.
Если таких людей, несколько, то программа должна вывести их
количество.
5
Иванов Сергей 27.03.1993
Сергеев Иван 12.05.1994
Петров Сидор 24.11.1995
Семенов Сергей 12.10.1994
Куликов Василий 27.03.1992
Куликов Василий
2
Иванов Сергей 27.03.1993
Сергеев Иван 27.03.1993
2
IDE
J: Взаимный индекс
Взаимным индексом совпадения строк \(S_1\) и \(S_2\), которые включают только
латинские буквы, называется величина
$$
I(S_1, S_2) = \displaystyle\frac{\sum\limits_{k=1}^{26} f_1(k) \cdot f_2(k)}{n_1 \cdot n_2},
$$
где \(n_1\) и \(n_2\) – длины строк \(S_1\) и \(S_2\), а \(f_i(k)\) – число вхождений буквы,
имеющей номер k в латинском алфавите, в строку \(S_i\).
Например, индекс совпадений строк «Moloko» и «mAma» равен
$$
I(«Moloko»,«mAma») = \displaystyle\frac{1\cdot 2}{6 \cdot 4} = \displaystyle\frac{1}{12}.
$$
(одна общая буква «m» встречается 1 раз в первой строке и 2 раза во
второй строке). Напишите программу, которая вводит
две строки и вычисляет взаимный индекс совпадения этих строк.
Любые символы, отличные от латинских букв, при вычислении индекса следует игнорировать,
а также в длине строки не учитывать.
Moloko!
mAma, %%%!
1/12
IDE
K: Большой треугольник
На плоскости дан набор точек с целочисленными координатами. Необходимо
найти такой треугольник наибольшей площади с вершинами в этих точках, у
которого нет общих точек с осью Оу, а одна из сторон лежит на оси Ох.
Напишите эффективную, в том числе по памяти, программу, которая будет
решать эту задачу. Размер памяти, которую использует Ваша программа, не
должен зависеть от количества точек.
В первой строке вводится одно целое положительное число - количество
точек N.
Каждая из следующих N строк содержит два целых числа - сначала
координата х, затем координата у очередной точки. Числа разделены
пробелом.
Программа должна вывести одно число - максимальную площадь треугольника,
удовлетворяющего условиям задачи. Если такого треугольника не
существует, программа должна вывести ноль.
8
-10 0
2 0
0 4
3 3
7 0
5 5
4 0
9 -9
22.5
3
1 1
2 1
2 2
0
IDE
L: Гоночная трасса
Гоночная трасса состоит из двух основных дорог и нескольких
переездов, позволяющих перейти с одной дороги на другую.
На всех участках, включая переезды, движение разрешено только
в одну сторону, поэтому переезд возможен только с дороги A на
дорогу B. Гонщик стартует в точке A0 и должен финишировать в
точке BN. Он знает, за какое время сможет пройти каждый участок пути по каждой дороге, то есть время прохождения участков A0A1, A1A2, ..., AN-1AN, B0B1, B1B2, ..., BN-1BN. Время прохождения всех переездов A0B0, A1B1, ..., ANBN одинаково и известно гонщику. Необходимо определить, за какое минимальное время гонщик сможет пройти трассу.
Напишите программу для решения этой задачи.
В первой строке задаётся количество участков трассы N.
Во второй строке задаётся целое число t – время (в секундах)
прохождения каждого из переездов A0B0, A1B1, …, ANBN. В каждой
из последующих N строк записано два целых числа ai и bi,
задающих время (в секундах) прохождения очередного участка
на каждой из дорог. В первой из этих строк указывается время
прохождения участков A0A1 и B0B1, во второй – A1A2 и B1B2 и
т. д.
Программа должна напечатать одно целое число: минимально возможное
время прохождения трассы (в секундах).
3
20
320 150
200 440
300 210
750
IDE
M: Специалист по безопасности
Специалист по безопасности дизассемблировал код вируса, и получил N строчек,
в каждой из которых записано 4 слова из 4 заглавных латинских букв.
Для дальнейшего анализа ему необходимо отсортировать эти сточки: сначала по возрастанию первого слова,
затем по убыванию второго слова, затем по возрастанию третьего, и наконец по убыванию четвёртого.
Напишите программу, которая поможет ему в этом.
На спутнике «Фотон» установлен прибор, предназначенный для измерения энергии космических лучей. Каждую минуту прибор передаёт по каналу связи неотрицательное вещественное число — количество энергии, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь.
Необходимо найти в заданной серии показаний прибора минимальное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут.
Каждая строка входных данных содержит одно неотрицательное вещественное число – очередное показание прибора. Общее количество строк не меньше 7.
Программа должна вывести одно число – описанное в условии произведение.
12
45
5.5
4
25
23
21
20
10
12
26
48.0
IDE
O: Призеры олимпиады
В олимпиаде участвовало N человек, каждый из которых мог набрать от 0 до 100 баллов. По положению об олимпиаде жюри может наградить не более 45% от числа участников, округляя их число до целого при необходимости вниз.
При этом если последний участник, попавший в 45% набирает столько же баллов, сколько первый участник, не попавший в 45%, то решение по этим участникам, и всем участникам, набравшим такой балл принимается следующим образом:
Все данные участники объявляются призерами, если набранный ими балл больше половины от максимально возможного балла.
Все эти участники не объявляются призерами, если набранный ими балл не больше половины от максимально возможного.
Программа получает на вход информацию об участниках олимпиады (один участник - в одной строке). Строка содержит имя участника (текстовая строка с произвольным числом пробелов) и набранный данным участником балл через пробел.
Программа должна вывести минимальный балл, который получил участник олимпиады, ставший ее призером.
Иванов Сергей 70
Сергеев Петр 30
Петров Василий 40
Васильев Андрей 80
Андреев Денис 50
Денисов Роман 90
Романов Иван 70
Ким Чен Ир 60
Ким Ир Сен 100
70
Иванов Сергей 50
Сергеев Петр 70
Петров Василий 40
Васильев Андрей 10
Андреев Денис 50
Денисов Роман 20
Романов Иван 30
Ким Чен Ир 70
Ким Ир Сен 100
70
Иванов Сергей 30
Сергеев Петр 60
Петров Василий 20
Васильев Андрей 100
Андреев Денис 30
Денисов Роман 80
Романов Иван 20
Ким Чен Ир 40
Ким Ир Сен 10
40
IDE
P: Среднемесячная температура
На вход программы подается 366 строк, которые содержат информацию о
среднесуточной температуре всех дней некоторого високосного года. Формат каждой из строк
следующий: сначала записана дата в виде mm.dd (на запись номера дня и
номера месяца в числовом формате отводится строго два символа, день от
месяца отделен точкой), затем через пробел записано значение
температуры — число со знаком плюс или минус, с точностью до 1 цифры
после десятичной точки. Данная информация отсортирована по значению
температуры, то есть хронологический порядок нарушен. Требуется
написать программу, которая будет выводить
на экран информацию о месяце (месяцах), среднемесячная температура у
которого (которых) наименее отклоняется от среднегодовой. В первой
строке вывести среднегодовую температуру. Найденные значения для
каждого из месяцев следует выводить в отдельной строке в виде: номер
месяца, значение среднемесячной температуры, отклонение от
среднегодовой температуры.
Пример данных:
01.16 -12.7
01.14 -12.3
...
07.24 +29.2
5.3
04 5.9 0.6
09 5.9 0.6
В данном тесте температура в месяце i каждый день равна i.
На вход программе подаются сведения о студентах некоторого вуза. В
первой строке сообщается количество студентов N (не более 100). Каждая
из следующих строк имеет формат:
<фамилия> <имя> <курс> <стипендия>
Все данные в строке разделяются одним пробелом. Фамилия состоит не
более, чем из 20 символов, имя – не более, чем из 15. Курс – целое
число от 1 до 5, стипендия – целое число. Требуется написать
программу, которая будет выводить фамилии и имена всех студентов,
имеющих максимальные стипендии на каждом курсе.
В рамках одного курса студенты должны выводиться отсортированными по ФИО.
Гарантируется, что число студентов, получающих максимальную стипендию на каждом курсе не превосходит 100.
6
Семенов Илья 3 2800
Петров Иван 1 2700
Иванов Сидор 1 2700
Смирнов Максим 3 4300
Иванов Сергей 1 2600
Смирнов Павел 3 4200
Курс 1
Иванов Сидор
Петров Иван
Курс 3
Смирнов Максим
IDE
R: Результаты переписи
В одном из городов Российской Федерации была произведена перепись населения.
Местный дворец творчества решил разослать приглашения всем детям от 10 до 14 лет.
Для этого необходимо отсортировать файл с результатами переписи по убыванию даты рождения.
Люди с одинаковой датой рождения должны быть отсортированы по алфавиту.
На вход даётся число N — количество жителей в переписи. Далее идёт N строчек в формате
ДД.ММ.ГГГГ Фамилия Имя
Программа должна отсортировать этот список в указанном порядке.
5
04.07.2009 Иванов Фёдор
14.12.2013 Кузькина Елена
04.07.2009 Иванов Борис
14.12.2013 Якубова Эльвира
31.12.1913 Стадов Семён
14.12.2013 Кузькина Елена
14.12.2013 Якубова Эльвира
04.07.2009 Иванов Борис
04.07.2009 Иванов Фёдор
31.12.1913 Стадов Семён
S: Остановки
Некоторый поезд в пути следования останавливается на N станциях (станция
номер 1 — начальная, а станция номер N — конечная). Дан список
пассажиров поезда, для каждого из которых известно, на какой станции он
садится, а на какой — выходит. Напишите программу, которая по этим данным определяет, на
каких перегонах (то есть между какими соседними станциями) в поезде было
наименьшее число пассажиров. На вход программе в первой сроке подается
количество станций N и количество пассажиров P. В каждой из последующих
P строк находится информация о пассажирах в следующем формате:
где <Фамилия> – строка, состоящая не более, чем из 20 символов без
пробелов, <Имя> – строка, состоящая не более, чем из 20 символов без
пробелов, <станция посадки> и <станция выхода> — числа от 1 до N, при
этом номер станции посадки меньше номера станции выхода.
Программа должна вывести список перегонов, на которых в поезде было
наименьшее число пассажиров. Каждый перегон выводится в виде двух
последовательных номеров станций, разделенных знаком “-“.
При выполнении задания следует учитывать, что значение N не превосходит
100, а значение P может быть большим.
6 3
Иванов Сергей 2 4
Сергеев Петр 1 3
Петров Кирилл 3 6
1-2
4-5
5-6
IDE
T: Многоборье
В соревнованиях по многоборью (из M видов спорта, M < 100) участвуют N
спортсменов. На вход программе в первой строке подается
число спортсменов N, во второй – число видов спорта M. В каждой из
последующих N строк находится информация в следующем формате:
<Фамилия> <Имя> <Баллы>
где <Фамилия> – строка, состоящая не более, чем из 20 символов без
пробелов, <Имя> – строка, состоящая не более, чем из 12 символов без
пробелов, <Баллы> – M целых чисел, обозначающие количество баллов,
набранных спортсменом в каждом из видов многоборья.
<Фамилия> и <Имя>, <Имя> и <Баллы>, а также отдельные числа в поле
<Баллы> разделены ровно одним пробелом.
Программа должна выводить результирующую таблицу, содержащую список
спортсменов, отсортированный по убыванию суммы баллов, набранные суммы
и занятые места.
Спортсмены, набравшие одинаковое количество баллов, должны быть отсортированы по ФИО.
3
4
Иванов Сергей 100 30 78 13
Петров Антон 90 16 98 14
Сидоров Юрий 100 70 30 21
Иванов Сергей 221 1
Сидоров Юрий 221 1
Петров Антон 218 2
IDE
U: Шифровка
На вход программе подается строка, в
которой нужно зашифровать все английские слова (словом называется
непрерывная последовательность английских букв, слова друга от друга
отделяются любыми другими символами, длина слова не превышает 100
символов). Строка заканчивается символом #, других символов # в строке
нет. Каждое слово зашифровано с помощью циклического сдвига на длину
этого слова. Например, если длина слова равна K, каждая буква в слове
заменяется на букву, стоящую в английском алфавите на K букв дальше
(алфавит считается циклическим, то есть, за буквой Z стоит буква A).
Строчные буквы при этом остаются строчными, а прописные – прописными.
Символы, не являющиеся английскими буквами, не изменяются.
Требуется написать программу, которая будет выводить на экран текст
зашифрованного сообщения.
Day, mice. "Year" is a mistake#
Gdb, qmgi. "Ciev" ku b tpzahrl#
IDE
V: Палиндром
Дана строка, состоящая только из заглавных латинский букв, заканчивающаяся точкой. Других точек в строке нет.
Используя все или некоторые символы этой строки (не считая точки) составьте строку максимальной длины, являющуюся палиндромом (то есть одинаково читающуюся слева направо и справа налево). Если таких строк несколько, то выведите минимальный в лексикографическом порядке палиндром.
PARALLELOGRAM.
ALRARLA
ONE.
E
IDE
W: Проходной балл
Для поступления в вуз абитуриент должен предъявить результаты трех экзаменов в виде ЕГЭ, каждый из них оценивается целым числом от 0 до 100 баллов. При этом абитуриенты, набравшие менее 40 баллов (неудовлетворительную оценку) по любому экзамену из конкурса выбывают. Остальные абитуриенты участвуют в конкурсе по сумме баллов за три экзамена.
В конкурсе участвует N человек, при этом количество мест равно K. Определите проходной балл, то есть такое количество баллов, что количество участников, набравших столько или больше баллов не превосходит K, а при добавлении к ним абитуриентов, набравших наибольшее количество баллов среди непринятых абитуриентов, общее число принятых абитуриентов станет больше K.
Программа получает на вход количество мест K. Далее идут строки с информацией об абитуриентах, каждая из которых состоит из имени (текстовая строка содержащая произвольное число пробелов) и трех чисел от 0 до 100, разделенных пробелами.
Программа должна вывести проходной балл в конкурсе. Выведенное значение должно быть минимальным баллом, который набрал абитуриент, прошедший по конкурсу.
Также возможны две ситуации, когда проходной балл не определен.
Если будут зачислены все абитуриенты, не имеющие неудовлетворительных оценок, программа должна вывести число 0.
Если количество абитуриентов, имеющих равный максимальный балл больше чем K, программа должна вывести число 1.
5
Иванов Сергей 70 70 70
Сергеев Петр 100 100 0
Петров Василий 70 60 70
Васильев Андрей 70 60 70
Андреев Денис 100 30 100
Денисов Роман 50 50 50
Романов Иван 60 70 70
Ким Чен Ир 50 50 50
Ким Ир Сен 40 40 40