Тип задач #26: Обработка данных с помощью сортировки

Сервис такси составляет рейтинг водителей для премирования.
Для каждого водителя в списке указаны количество отрицательных отзывов и количество положительных отзывов за определённое время работы.
Все водители в списке пронумерованы, начиная с единицы.
В рейтинговом списке администраторы располагают водителей по следующему алгоритму:
– Все 2N чисел, обозначающих количество отрицательных и положительных отзывов для N водителей, упорядочивают по возрастанию;
– Если минимальное число в этом упорядоченном списке – количество отрицательных отзывов,
то водитель в рейтинге занимает первое свободное место от его начала;
– Если минимальное число – количество положительных отзывов, то водитель занимает первое свободное место от конца рейтинга;
– Если число обозначает количество отрицательных или положительных отзывов уже размещённого в рейтенге водителя, то это число не принимают во внимание при формировании рейтинга.
Рейтинг водителей - порядковый номер водителя в итоговом списке. Рейтинг начинается с единицы.
Этот алгоритм применяется последовательно для размещения всех N водителей.

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

Определите и запишите в ответе три числа:
– Номер последнего водителя, для которого будет определено его место в рейтинге.
– Место в рейтинге водителя, для которого будет определено его место в рейтинге последним.
– Количество водителей, которые займут в рейтинге более низкие места.

📁 Файл для задачи

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

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

Входные данные:
В первой строке 2 натуральных числа: N (N≤4000) - количество товаров, которые заказал человек и M (M≤4000) - количество пакетов в доступе.
В следующих N строках находиться информация о весе товаров. А в следующих M строках - информация грузоподъёмности каждого отдельного пакета.
(Вес любого товара и грузоподъёмность любого пакета не превышают 150)

Типовой пример организации данных во входном файле: 2 3
70
140
80
90
139\

Ответом для данного примера будет - 1 80 (товар весом 140 мы унести не можем, а минимальный пакет для товара с весом 70 - 80).
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

📁 Файл для задачи

Входной файл содержит заявки на печать на 3D-принтере в течение одних суток.
Каждая заявка задаётся двумя числами — временем начала и временем окончания печати в минутах от начала суток (0–1440).
Если время печати двух или более заявок пересекается, то выполнить можно только одну из них.
Между окончанием одной печати и началом следующей должен быть перерыв не менее 2 минут — для охлаждения и подготовки принтера к следующему заданию.

Какое максимальное количество печатей можно выполнить в этот день?
Каким при этом может быть максимально возможный перерыв между двумя последними печатями?

В ответе запишите два числа - максимальное количество печатей и максимально возможный перерыв между двумя последними печатями.

Файл содержит данные о заявках на печать. Каждая строка содержит данные одной заявки - два натуральных числа (время начала и время окончания печати)

📁 Файл для задачи

Для дачных участков СНТ необходимо закупить снегоуборщики. Для каждого из N участков будет куплен свой снегоуборщик. Известны минимальные требования к мощности этой техники для каждого из участков.
Для закупки доступно К моделей снегоуборщиков определённой мощности и стоимости. Количество экземпляров каждой модели не ограничено. Для каждого участка выбирается снегоуборщик минимальной стоимости, мощность которого не меньше требуемой; при одной и той же стоимости выбирается модель максимальной мощности.

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

Входные данные
Первая строка входного файла содержит два натуральных числа: N (1 < N < 1 000 000) - количество участков CHT и К (1 < K < 100 000) - количество моделей снегоуборщиков соответственно. Следующие N строк содержат по одному натуральному числу, не превышающему 1000, минимальные мощности снегоуборщиков, которые можно закупить для каждого из N участков. Далее в каждой из К строк содержится пара натуральных чисел - мощность очередной модели снегоуборщика и её стоимость соответственно. Мощность снегоуборщиков не превосходит 1000, стоимость - 100 000. Гарантируется, что любые две модели снегоуборщиков различаются по мощности или по стоимости. Закупить подходящий набор снегоуборщиков всегда можно.
Выходные данны\е В ответе укажите два искомых числа: суммарную стоимость всех купленных снегоуборщиков и максимальную мощность среди них.

Типовой пример организации данных во входном файле
3 4
1
2
3
10 7
1 5
3 7
2 3
При таких исходных данных для первого и второго участков оптимально закупить одинаковые снегоуборщики мощностью 2 и стоимостью 3, для третьего участка будет закуплен снегоуборщик мощностью 10. Стоимость закупки составит 3 + 3 + 7 = 13. Ответ: 13; 10.\

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

📁 Файл для задачи

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

• все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию;
• если минимальное число в этом упорядоченном списке – срок хранения, то продукт в рейтинге занимает первое свободное место от его начала;
• если минимальное число – срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга;
• если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание. Этот алгоритм применяется последовательно для размещения всех N продуктов.

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

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

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

📁 Файл для задачи

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

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

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

Типовой пример организации входных данных
9
41 3
43 125
50 33
42 125
42 126
42 127
41 125
50 126
42 126
Для приведённого примера точку с номером 125 посетили три спортсмена с номерами 41, 42 и 43. Ответом является пара чисел: 3; 125.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

📁 Файл для задачи

Входной файл содержит информацию о заявках граждан, обращающихся во многофункциональный центр (МФЦ) в течение календарных суток. В заявке указаны время начала и время окончания приёма специалистом (в минутах от начала суток).
Рабочие места специалистов МФЦ (окна) пронумерованы натуральными числами начиная с 1. Приём одного гражданина ведёт свободный специалист в окне с минимальным номером. Новый посетитель может обратиться к освободившемуся специалисту начиная со следующей минуты после завершения приёма предыдущего. Если в момент обращения в МФЦ свободных специалистов нет, то гражданин уходит.

Определите, сколько граждан смогут попасть на приём в МФЦ в течение 24 ч, и каков номер окна специалиста, который начнёт принимать посетителя последним. Если таких окон несколько, укажите наименьший номер окна.

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

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

Типовой пример организации данных во входном файле
2
5
30 60
40 100
59 60
61 100
101 144
При таких исходных данных воспользоваться услугами МФЦ смогут первый, второй, четвёртый и пятый граждане. Наименьший номер окна, где последний из граждан будет принят специалистом, - 1, так как будут свободны окна 1 и 2.

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

📁 Файл для задачи

На производстве штучных изделий N деталей должны быть отшлифованы и окрашены. Для каждой детали известно время её шлифовки и время окрашивания. Детали пронумерованы начиная с единицы. Параллельная обработка деталей не предусмотрена. На ленте транспортёра имеется N мест для каждой из N деталей.

На ленте транспортёра детали располагают по следующему алгоритму:
— все 2N чисел, обозначающих время окрашивания и шлифовки для N деталей, упорядочивают по возрастанию;
— если минимальное число в этом упорядоченном списке — это время шлифовки конкретной детали, то деталь размещают на ленте транспортёра на первое свободное место от её начала;
— если минимальное число — это время окрашивания, то деталь размещают на первое свободное место от конца ленты транспортёра
— если число обозначает время окрашивания или шлифовки уже рассмотренной детали, то его не принимают во внимание.
Этот алгоритм применяется последовательно для размещения всех N деталей.

Определите номер последней детали, для которой будет определено её место на ленте транспортёра, и количество деталей, которыебудут отшлифованы до неё.

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

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

Типовой пример организации данных во входном файле
5
30 50
100 155
150 170
10 160
120 55
При таких исходных данных порядок расположения деталей на ленте транспортёра следующий: 4, 1, 2, 3, 5. Последней займёт своё место на ленте транспортёра деталь 3. При этом до неё будут отшлифованы три детали.

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

📁 Файл для задачи

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

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

📁 Файл для задачи

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны меньше длины стороны другой коробки не менее чем на 9 единиц. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.

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

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

📁 Файл для задачи