№ 84ZCYP (Уровень сложности: Повышенный)
Отдел маркетинга сети магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы.
В рейтинговом списке маркетологи располагают продукты по следующему алгоритму:
- все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию;
- если минимальное число в этом упорядоченном списке – срок хранения, то продукт в рейтинге занимает первое свободное место от его начала;
- если минимальное число – срок годности к употреблению, то продукт занимает первое свободное место от конца рейтинга;
- если число обозначает срок хранения или срок годности к употреблению уже рассмотренного продукта, то его не принимают во внимание.
Этот алгоритм применяется последовательно для размещения всех N продуктов.
Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более низкие места.
Входные данные
В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество продуктов. Следующие N строк содержат пары чисел, обозначающих соответственно срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки (все числа натуральные, различные).
Выходные данные
Запишите в ответе два натуральных числа: сначала номер последнего продукта, для которого будет определено его место в рейтинге, затем – количество продуктов, которые займут в рейтинге более низкие места.
Типовой пример организации данных во входном файле приведён в приложении.
Типовой пример организации данных во входном файле приводится только в демонстрационном варианте ЕГЭ!
Файлы к заданию:
Правильный ответ:
| № | 1 | 2 |
|---|---|---|
| 1 | 564 | 444 |