Задание 26 ЕГЭ по информатике

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

На ленте транспортёра имеются $N$ мест для каждой из $N$ деталей. Места для деталей пронумерованы начиная с единицы.

На ленте транспортёра детали располагают по следующему алгоритму:

• все $2*N$ чисел, обозначающих время окрашивания и шлифовки для $N$ деталей, упорядочивают по возрастанию;

• если минимальное число в этом упорядоченном списке — это время шлифовки конкретной детали, то деталь размещают на ленте транспортёра на первое свободное место о её начала;

• если минимальное число — это время окрашивания, то деталь размещают на первое свободное место от конца ленты транспортера;

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

Этот алгоритм применяется последовательно для размещения всех $N$ деталей.

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

Входные данные

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

Выходные данные

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

Типовой пример организации данных во входном файле

5 

30 50 

100 155 

150 170 

10 160 

120 55 

При таких исходных данных порядок расположения деталей на ленте транспортёра следующий: 4, 1, 2, 3, 5. Последней займёт своё место на ленте деталь 3. При этом до неё будут отшлифованы три детали.

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

Файл к заданию: https://drive.google.com/file/d/1CvuualBIZrVH4bp758z953fsmLdNksaL/view?usp=drive_link