Рейтинг продуктов по срокам
Отдел маркетинга сети продуктовых магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы.
В рейтинговом списке продукты располагают по следующему алгоритму: все $2N$ чисел, обозначающих срок хранения и срок годности к употреблению для $N$ продуктов, упорядочивают по возрастанию. Если минимальное число в этом упорядоченном списке обозначает срок хранения, продукт занимает первое свободное место от начала рейтинга. Если минимальное число обозначает срок годности к употреблению, продукт занимает первое свободное место от конца рейтинга. Если число обозначает срок хранения или годности к употреблению уже рассмотренного продукта, его не принимают во внимание. Алгоритм применяется последовательно для размещения всех $N$ продуктов.
Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более высокие места.
В первой строке входного файла находится натуральное число $N$ ($N \leq 1000$). Следующие $N$ строк содержат пары различных натуральных чисел: срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки.
Используйте данные из прилагаемого входного файла. Запишите два натуральных числа: сначала номер последнего продукта, для которого определено место в рейтинге, затем количество продуктов, занявших более высокие места.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Смоделируйте последовательный просмотр всех $2N$ сроков после сортировки по возрастанию. Для каждого продукта храните признак: был ли он уже размещён.
2Наводящая — какие числа считатьуровень 2 из 3
При первом появлении срока хранения продукт ставится на ближайшее свободное место слева, а при первом появлении срока годности — на ближайшее свободное место справа.
3Прямая — фактически решениеуровень 3 из 3
После обработки каждого числа фиксируйте номер продукта, если он только что получил место, и сам номер занятого места. Последнее такое событие даёт первый ответ, а число занятых мест левее него — второй.