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

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

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

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

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

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

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

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

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

Определите сколько деталей будет отшлифовано, и деталь с каким номером окажется на позиции с номером $K$ на ленте транспортёра.

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

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

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

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

5 3

30 50

100 155

150 170

10 160

120 55

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

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

Файл к заданию: https://storage.yandexcloud.net/100points-bank/informatics-ege/files/12933_26.txt