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