Информатика. ЕГЭ
Задания для подготовки
Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников
Задачи разных лет из реальных экзаменов, демо-вариантов, сборников задач и других источников
При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами. В ответе запишите два целых числа: искомый номер ряда и наименьший номер места в найденной паре. Нумерация рядов и мест ведётся с \(1.\) Гарантируется, что хотя бы одна такая пара в зале есть.
Входные данные
В первой строже входного файла находятся три числа: \(N\) — количество занятых мест в зале (целое положительное число, не превышающее \(10~000),\) \(M\) — количество рядов (целое положительное число, не превышающее \(100~000)\) и \(K\) — количество мест в каждом ряду (целое положительное число, не превышающее \(100~000).\) В следующих \(N\) строках находятся пары натуральных чисел: номер ряда и номер места занятого кресла соответственно (первое число не превышает значения \(M,\) а второе — \(K).\)
Выходные данные
Два целых положительных числа: наибольший номер ряда и наименьший номер места в найденной паре кресел.
Типовой пример организации данных во входном файле
\(7 \, 7 \, 8\)
\(1 \, 1\)
\(6 \, 6\)
\(5 \, 5\)
\(6 \, 7\)
\(4 \, 4\)
\(2 \, 2\)
\(3 \, 3\)
При таких исходных данных ответом является пара чисел \(5\) и \(6.\) Условию задачи удовлетворяют места \(6\) и \(7\) в ряду \(5:\) перед креслами \(6\) и \(7\) нет занятых мест и это первая из двух возможных пар в этом ряду. В рядах \(6\) и \(7\) искомую пару найти нельзя.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Во время сессии студенты сдают 4 экзамена, за каждый из которых можно получить от 2 до 5 баллов. Студенты, получившие хотя бы одну «двойку», считаются не сдавшими сессию. Результаты сессии публикуются в виде рейтингового списка, в котором сначала указаны идентификационные номера студентов (ID), сдавших сессию, в порядке убывания среднего балла за сессию, а в случае равенства средних баллов – в порядке возрастания ID. Затем располагаются ID студентов, не сдавших сессию: сначала – получивших одну «двойку», затем – две «двойки», потом ID студентов с тремя «двойками» и, наконец, ID студентов, получивших по 2 балла за каждый из экзаменов. Если студенты имеют одинаковое количество «двоек», то их ID в рейтинге располагаются в порядке возрастания.
Повышенную стипендию получают студенты, занявшие в рейтинговом списке первые 25 % мест, при условии отсутствия у них «двоек». Гарантируется, что без «двоек» сессию сдали не менее 25 % студентов.
Найдите ID студента, который занимает последнее место среди студентов с повышенной стипендией, а также ID первого в рейтинговом списке студента, который имеет более двух «двоек».
В ответе запишите два целых положительных числа: сначала ID студента, который занимает последнее место среди студентов с повышенной стипендией, затем ID первого в рейтинговом списке студента, который имеет более двух «двоек».
Входные данные
В первой строке входного файла находится число \(N\), обозначающее количество студентов (целое положительное число, не превышающее \(10~000\)). Каждая из следующих \(N\) строк содержит \(5\) чисел через пробел: ID студента (целое положительное число, не превышающее \(100~000\)) и четыре оценки, полученные им за сессию. Гарантируется, что общее число студентов \(N\) кратно \(4\) и хотя бы один студент имеет более двух «двоек». Во входном файле все ID различны.
Выходные данные
Два натуральных числа: искомые ID студентов в порядке, указанном в условии задачи. Типовой пример организации данных во входном файле
\(8\)В банке дистанционной проверяющей системы имеется более \(100~000\) заданий. Все задачи пронумерованы начиная с единицы. Эти задания в течение учебного периода решают участники различных курсов. Каждому студенту при регистрации присваивается уникальный идентификатор — натуральное число, не превышающее \(1~000~000.\) Студент может сдать несколько различных правильных решений одной задачи, при этом в зачёт идёт только одно из них.
Преподаватель сделал выгрузку результатов за некоторый период времени и выбрал студента, который решил наибольшее количество задач из банка с идущими подряд номерами, не пропустив ни одной.
Определите идентификационный номер студента, который решил наибольшее количество задач с идущими подряд номерами, и количество решённых им задач. Если несколько студентов решили одинаковое максимальное количество задач, то укажите наименьший идентификационный номер.
Входные данные
В первой строке входного файла находится число \(N\) — количество зачтённых решений (натуральное число, не превышающее \(60~000\)) за некоторый период времени. Каждая из следующих \(N\) строк содержит два натуральных числа, не превышающих \(100~000\): идентификатор студента и номер правильно решённой задачи.
Выходные данные
Два целых неотрицательных числа: наименьший идентификационный номер студента и наибольшее количество успешно решённых задач с подряд идущими номерами.
Система наблюдения ежеминутно фиксирует вход и выход сотрудников из офиса (в минутах, прошедших от начала суток). Считается, что в моменты фиксации входа и выхода сотрудник находится в офисе. Нулевая минута соответствует моменту начала рабочего дня в офисе, который длится \(24\) ч в сутки без перерыва. Менеджер компании анализирует данные системы наблюдения за прошедшие сутки, и выявляет непересекающиеся отрезки времени наибольшей длины, в течение которых число сотрудников, находящихся в офисе, не изменялось. Входной файл содержит время входа и выхода каждого сотрудника компании. Определите минуту, когда в предпоследний раз за сутки число сотрудников поменялось, и укажите наибольшую длину отрезка времени, когда количество сотрудников оставалось неизменным.
Входные данные
В первой строке входного файла находится натуральное число \(N\) \((N \leqslant 100~000)\) — количество сотрудников компании. Следующие \(N\) строк содержат пары чисел, обозначающих соответственно время входа и время выхода сотрудника (все числа натуральные, не превышающие \(1440\)).
Запишите в ответе два натуральных числа: сначала минуту, когда в предпоследний раз за сутки число сотрудников поменялось, а затем наибольшую длительность промежутка времени, при котором количество сотрудников оставалось неизменным.
Типовой пример организации данных во входном файле
\(5\)
\(10 \, 1070\)
\(230 \, 1070\)
\(240 \, 1070\)
\(1070 \, 1400\)
\(1071 \, 1400\)
При таких исходных данных в течение суток было \(7\) промежутков времени, когда число сотрудников не менялось: \((0, \, 10),\) \((10, \, 230),\) \((230, \, 240),\) \((240, \, 1070),\) \((1070, \, 1071),\) \((1071, \, 1400),\) \((1400, \, 1440).\) Наибольшей длиной из этих отрезков является число \(830.\) В \(1071\) минуту в предпоследний раз за сутки изменилось число сотрудников.
На складе предприятия имеются заготовки двух видов: \(A\) и \(B,\) у каждой заготовки есть размер, измеряемый в миллиметрах. Для производства одного изделия необходима одна заготовка типа \(A\) и одна заготовка типа \(B,\) при этом разность размеров этих заготовок должна быть не более \(20\) мм. Прибыль от продажи полученного изделия численно равна сумме размеров использованных заготовок.
Руководство предприятия хочет использовать имеющиеся заготовки так, чтобы получить максимальную прибыль. Определите, сколько изделий для этого нужно произвести и какая прибыль будет получена.
Входные данные
Первая строка входного файла содержит целое число \(N\) — общее количество изделий на складе. Каждая из следующих \(N\) строк содержит букву \(A\) или \(B,\) определяющую тип заготовки, и целое число — размер этой заготовки. В ответе запишите два целых числа: сначала количество произведённых изделий, затем полученную прибыль.При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером \(100~000\) на \(100~000\) точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от \(1\) до \(100~000\)) и номер позиции в ряду (целое число от \(1\) до \(100~000\)). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, – тёмной.
При анализе результатов эксперимента рассматривают изолированные точки. Точка называется изолированной, если эта точка светлая (независимо от того, сколько частиц в неё попало), а другие светлые точки в том же ряду либо отсутствуют, либо находятся на расстоянии более \(500.\) Вам необходимо по заданному протоколу определить наибольшее количество изолированных точек, расположенных в одном ряду, и номер ряда, в котором это количество встречается. Если таких рядов несколько, укажите максимально возможный номер.
Входные данные
Первая строка входного файла содержит целое число \(N\) – общее количество частиц, попавших на экран. Каждая из следующих \(N\) строк содержит \(2\) целых числа: номер ряда и номер позиции в ряду. В ответе запишите два целых числа: сначала максимальное количество изолированных точек в одном ряду, затем – номер ряда, в котором это количество встречается.