Задания для подготовки к ЕГЭ Сортировка

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

Входные данные
Первая строка входного файла содержит целое число N (N ⩽ 2000) - количество заявок на уборку снега. Следующие N строк содержат
пары чисел, обозначающих начало участка (в метрах от начала дороги) и его протяжённость. Каждое из чисел натуральное, не
превосходящее 10 000. Гарантируется, что конец участка не выходит за пределы дороги.
В ответе запишите два целых числа: сначала наибольшее количество заявок, которые может выполнить управляющая компания, затем - минимально возможную при таком количестве заявок длину неубранного участка, расположенного конце дороги (в метрах).
Типовой пример организации данных во входном файле
5
1 1000
1001 1000
2001 2500
4501 500
4501 1500
При таких исходных данных будет выполнено не более 4 заявок. Могут быть выполнены заявки с номерами 1, 2, 3 и 4 или заявки с номерами 1, 2, 3 и 5. Ответ: 4 3999.

В одном городе есть более 100 жилых домов. Все дома пронумерованы, начиная с единицы. Управляющая компания получила заявки на капитальный ремонт от жителей домов. В заявке указан номер дома и номер подъезда, где требуется ремонт, при этом каждой заявке присваивается уникальный идентификатор – натуральное число, не превышающее 1 000 000. На один и тот же подъезд могут быть заявки сразу от нескольких жителей.

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

Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 200 000) – количество полученных заявок на капитальный ремонт. Следующие N строк содержат три числа: номер заявки, номер дома и номер подъезда (все числа натуральные, не превышающие 1 000 000).

Выходные данные
Запишите в ответе два натуральных числа: сначала номер дома с максимальным количеством подряд идущих подъездов, затем номер последнего найденного подъезда из максимального числа подряд идущих подъездов в этом доме.

Для хранения двумерного цифрового растрового чёрно-белого изображения Петя сохранил в текстовом файле информацию о позициях всех пикселей чёрного цвета на изображении (номера рядов пикселей и номера чёрных пикселей в ряду). Для редактирования изображения Пете нужно изменить цвет с белого на чёрный всем имеющимся двум соседним белым пикселям, таким что слева и справа от них в том же ряду пиксели чёрные. Найдите ряд с наибольшим номером, в котором есть два соседних пикселя, удовлетворяющих требованию Пети. Гарантируется, что есть хотя бы один ряд, удовлетворяющий этому условию. 

Входные данные 
В первой строке входного файла находится число N - количество рядов пикселей (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 100 000: номер ряда и номер чёрного пикселя в ряду. 

Запишите в ответе два целых числа: номер ряда и наименьший номер пикселя в ряду из найденных в этом ряду подходящих пар белых пикселей.

В магазине для упаковки подарков есть N кубических коробок и М декоративных замочков к ним (M < N). Самой интересной считается упаковка подарка по принципу матрёшки - подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т. д., при этом к каждой коробке подбирается подходящий замочек. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 6 единиц меньше длины стороны другой коробки. Замочек подходит к коробке, если маркировка замочка совпадает с длиной стороны коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку. 

Входные данные 
B первой строке входного файла находятся число N - количество коробок в магазине (натуральное число, не превышающее 10 000) и через пробел число М - количество декоративных замочков в магазине (натуральное число, не превышающее 10 000). следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000) и через знак табуляции значения, указанные как маркировки на замочках (все числа натуральные, не превышающие 10 000), каждая пара таких значений - в отдельной строке; в последних N - М строках второе число, соответствующее маркировке замочка, опускается, и числа, соответствующие длинам сторон коробок, идут каждое в отдельной строке. 

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

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

Входной файл содержит сведения о размерах прямоугольников и их возможных положениях на плоскости. Для каждого прямоугольника указана целочисленная абсцисса положения его нижнего левого угла, длина горизонтальной стороны, длина вертикальной стороны. Если при размещении на плоскости один прямоугольник накрывает другой, то дети должны оставить только один из них. Если стороны прямоугольников касаются, то можно оставить на плоскости оба прямоугольника. Определите максимальное количество прямоугольников, которое могут разместить на плоскости дети, и какова при этом максимально возможная величина модуля разности абсцисс положений левых нижних углов двух прямоугольников, наиболее удалённых от начала координат. 

Входные данные 
В первой строке входного файла находится натуральное число N (N ≤ 1000) - количество прямоугольников. Следующие N строк содержат тройки чисел, обозначающих абсциссу положения левого нижнего угла прямоугольника на плоскости, длину его горизонтальной стороны, длину его вертикальной стороны. Каждое из чисел целое, не превосходящее 10 000. 

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

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

Входные данные 
В первой строке входного файла находится натуральное число N (N ≤ 1000) - количество заявок на проведение мероприятий. Следующие N строк содержат пары чисел, обозначающих время начала и длительность мероприятия. Каждое из чисел натуральное, не превосходящее 1440. 

Запишите в ответе два числа: максимальное количество мероприятий и самый длинный перерыв между двумя последними мероприятиями (в минутах).

Петя участвует в расширенной версии игры «Морской бой». В данной версии игры, в отличие от классической, допускается увеличение количества и длины кораблей, а игровое поле может быть прямоугольным, размером М × К, где М - количество горизонтальных рядов клеток на игровом поле (целое положительное число, не превышающее 100 000), К - количество вертикальных рядов клеток на игровом поле (целое положительное число, не превышающее 100 000). Нумерация горизонтальных рядов поля идёт сверху вниз с 1, а вертикальных - слева направо также с 1. Некоторые клетки поля уже заняты кораблями (п-палубный корабль занимает, соответственно, и подряд идущих клеток). Пете необходимо разместить 3-палубный корабль, расположив его на свободных клетках некоторого одного ряда так, чтобы корабль находился как можно дальше от верхнего края игрового поля и все клетки игрового поля, находящиеся непосредственно над ним, не были заняты другими кораблями. Допускается ставить корабли вплотную друг к другу. 

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

Входные данные. 
В первой строке входного файла находятся три числа: N - количество клеток игрового поля, в которых расположены однопалубные корабли или части многопалубных кораблей (N - целое положительное число, не превышающее 100 000), М - количество горизонтальных рядов игрового поля и К - количество вертикальных рядов игрового поля. В следующих N строках соответственно находятся пары натуральных чисел: номер горизонтального ряда и номер вертикального ряда игрового поля, в которых расположены корабли или их части (первое число не превышает значения М, а второе - K). 

Запишите в ответе два целых числа: номер горизонтального ряда и наибольший из трёх номеров вертикальных рядов, где необходимо разместить корабль.

При онлайн-покупке билета на концерт известно, какие места в зале уже заняты. Необходимо купить два билета на такие соседние места в одном ряду, чтобы перед ними все кресла с такими же номерами были свободны, а ряд находился как можно дальше от сцены. Если в этом ряду таких пар мест несколько, найдите пару с наименьшими номерами. В ответе запишите два целых числа: искомый номер ряда и наименьший номер места в найденной паре. Нумерация рядов и мест ведётся с 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 искомую пару найти нельзя.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

На складе необходимо отправить груз в один грузовик — коробки одинакового размера, но разной массы. Общая масса всех коробок превышает грузоподъёмность грузовика. Количество мест в грузовике не меньше числа коробок, подготовленных к отправке.

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

Входные данные
В первой строке входного файла находятся два числа: S — грузоподъёмность грузовика (натуральное число, не превышающее 100 000) и N — количество коробок (натуральное число, не превышающее 10 000).
В следующих N строках находятся значения масс коробок (все числа натуральные, не превышающие 100), каждое в отдельной строке.

Выходные данные
Два целых неотрицательных числа: минимальное количество коробок, которые нельзя отправить за один рейс, и максимальная суммарная масса оставшихся на складе коробок.
Типовой пример организации данных во входном файле
100 4
80
30
50
40
При таких исходных данных можно транспортировать за один раз максимум два контейнера. Возможные массы этих двух контейнеров - 30 и 40, 30 и 50 или 40 и 50. Контейнеры с массами 50 и 80 могут быть не перевезены. Ответом для приведённого примера является пара чисел 2 и 130.

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

Входные данные
Первая строка входного файла содержит целое число N (N ⩽ 2000) - количество заявок на уборку снега. Следующие N строк содержат
пары чисел, обозначающих начало участка (в метрах от начала дороги) и его протяжённость. Каждое из чисел натуральное, не
превосходящее 10 000. Гарантируется, что конец участка не выходит за пределы дороги.
В ответе запишите два целых числа: сначала наибольшее количество заявок, которые может выполнить управляющая компания, затем - максимально возможную при таком количестве заявок длину неубранного участка, расположенного конце дороги (в метрах).

Типовой пример организации данных во входном файле
5
1 1000
1001 1000
2001 2500
4501 500
4501 1500
При таких исходных данных будет выполнено не более 4 заявок. Могут быть выполнены заявки с номерами 1, 2, 3 и 4 или заявки с номерами 1, 2, 3 и 5. Ответ: 4 4999.

В кондитерской есть N круглых форм для коржей. Специализация кондитерской — многоярусные торты, в которых диаметр каждого верхнего коржа меньше диаметра предыдущего. Один корж можно поместить на другой, если его диаметр хотя бы на 5 единиц меньше диаметра другого коржа. Определите наибольшее количество коржей, которое можно использовать для создания многоярусного торта, и максимально возможный диаметр самого маленького коржа.

Входные данные: первая строка — N (не более 10 000). Следующие N строк — диаметры форм (натуральные числа, не превышающие 10 000).

Выходные данные: два числа — наибольшее количество коржей и максимально возможный диаметр верхнего коржа в таком торте.

Типовой пример (те же данные что в оригинале, но разница 5)
5
43 40 32 40 30

Подходящие наборы: 30 и 40 (разница 10 ≥ 5), 32 и 40 (разница 8 ≥ 5) — макс 2 коржа, верхний максимум 32.

Отбор кандидатов в матросы происходит по сумме баллов четырёх экзаменов. На заранее известное количество мест S отбираются кандидаты, набравшие большую сумму баллов по результатам четырёх экзаменов. Все кандидаты, набравшие определённую сумму или больше, зачисляются на имеющиеся места. Такой балл называется проходным. Если после заполнения мест кандидатами с проходным баллом остаются незаполненные места, но кандидатов, набравших следующую сумму баллов, больше чем вакантных мест, набранная ими сумма называется полупроходным баллом. Из числа кандидатов с полупроходным баллом на имеющиеся места принимаются кандидаты с более высоким баллом за собеседование, а при равенстве — с наименьшими ID.

Входные данные: первая строка — N и S (не более 1000). Каждая из следующих N строк содержит 6 чисел: ID, затем четыре оценки по экзаменам (0–100) и балл за собеседование (0–15).
Выходные данные: Определите ID последнего кандидата с проходным баллом и количество кандидатов, набравших полупроходной балл.

Участники викторины письменно отвечают на 8 вопросов различной сложности. За правильный ответ начисляется от 1 до 5 баллов в зависимости от сложности вопроса. За неверный ответ вычитается от 1 до 5 баллов. Участник может не отвечать на какой-то вопрос, в таком случае баллы за этот вопрос не начисляются.

По результатам викторины для каждого участника вычисляются три показателя: 1) сумма — общее количество набранных баллов; 2) плюсы — сумма баллов без учёта неверных ответов; 3) ответы — общее количество сданных ответов (верных и неверных).

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

Входные данные: первая строка — N (не более 10 000). Каждая из следующих N строк содержит 9 целых чисел: ID участника, затем баллы за каждый из 8 вопросов.
Выходные данные: Определите ID участника, занимающего в таблице первое место среди тех, кто не прошёл в следующий тур, а также количество участников, у которых все три показателя такие же, как у участника, занявшего в итоговой таблице 1000-е место (включая самого этого участника).

Каждый кандидат в отряд космонавтов проходит 4 испытания, за каждое из которых можно получить от 0 до 100 баллов. Кроме того, можно получить дополнительное от 0 до 15 баллов по итогам собеседования. Каждому кандидату присваивается уникальный ID — натуральное число, не превышающее 100 000. В отряде имеется фиксированное число мест K, на которые кандидаты зачисляются в порядке убывания их номера в рейтинговом списке. Рейтинговый список формируется по убыванию суммы набранных баллов, включая баллы за собеседование. При равенстве сумм выше стоит участник с большими баллами за собеседование, а при равенстве и этих баллов — с меньшим ID.

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

Входные данные: первая строка — N и K (не превышающие 10 000). Следующие N строк — ID и шесть чисел: четыре результата испытаний и результат собеседования.

Выходные данные: ID кандидата, последним из рейтингового списка набравшего проходной балл, затем количество кандидатов, набравших полупроходной балл (0 если отсутствует).

Во время сессии студенты сдают 5 экзаменов, за каждый из которых можно получить от 1 до 5 баллов. Студенты, получившие хотя бы одну «единицу», считаются не сдавшими сессию. Результаты публикуются в виде рейтингового списка: сначала — ID сдавших сессию в порядке убывания среднего балла (при равенстве — по возрастанию ID), затем — ID не сдавших: сначала получивших одну единицу, затем две, потом три и т.д. (при одинаковом количестве единиц — по возрастанию ID).

Повышенную стипендию получают студенты, занявшие первые 20% мест рейтинга, при условии отсутствия единиц. Гарантируется, что без единиц сессию сдали не менее 20% студентов.

Входные данные: первая строка — N (не более 10 000, кратно 5). Следующие N строк — ID и пять оценок через пробел.
Выходные данные: Найдите ID студента, занимающего последнее место среди студентов с повышенной стипендией, а также ID первого в рейтинге студента, имеющего более двух единиц.