Задание 26 ЕГЭ по информатике · 64AB6F
Рейтинг и проходной баллВысокаяКЭС 3.10
Отдел маркетинга сети продуктовых магазинов составляет рейтинг продуктов по информации об их сроках хранения с момента изготовления и после вскрытия упаковки. Для каждого продукта известен срок его хранения с момента изготовления и срок годности к употреблению после вскрытия упаковки. Продукты пронумерованы начиная с единицы.
В рейтинговом списке продукты располагают по следующему алгоритму: все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию. Если минимальное число в этом упорядоченном списке обозначает срок хранения, продукт занимает первое свободное место от начала рейтинга. Если минимальное число обозначает срок годности к употреблению, продукт занимает первое свободное место от конца рейтинга. Если число обозначает срок хранения или годности к употреблению уже рассмотренного продукта, его не принимают во внимание. Алгоритм применяется последовательно для размещения всех N продуктов.
Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более высокие места.
В первой строке входного файла находится натуральное число N (N≤1000). Следующие N строк содержат пары различных натуральных чисел: срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки.
Используйте данные из прилагаемого входного файла. Запишите два натуральных числа: сначала номер последнего продукта, для которого определено место в рейтинге, затем количество продуктов, занявших более высокие места.
1_64AB6F.zipВ рейтинговом списке продукты располагают по следующему алгоритму: все 2N чисел, обозначающих срок хранения и срок годности к употреблению для N продуктов, упорядочивают по возрастанию. Если минимальное число в этом упорядоченном списке обозначает срок хранения, продукт занимает первое свободное место от начала рейтинга. Если минимальное число обозначает срок годности к употреблению, продукт занимает первое свободное место от конца рейтинга. Если число обозначает срок хранения или годности к употреблению уже рассмотренного продукта, его не принимают во внимание. Алгоритм применяется последовательно для размещения всех N продуктов.
Определите номер последнего продукта, для которого будет определено его место в рейтинге, и количество продуктов, которые займут в рейтинге более высокие места.
В первой строке входного файла находится натуральное число N (N≤1000). Следующие N строк содержат пары различных натуральных чисел: срок хранения продукта с момента изготовления и срок годности к употреблению после вскрытия упаковки.
Используйте данные из прилагаемого входного файла. Запишите два натуральных числа: сначала номер последнего продукта, для которого определено место в рейтинге, затем количество продуктов, занявших более высокие места.
Показать ответ
9 464
Подсказки (3)
- Смоделируйте последовательный просмотр всех 2N сроков после сортировки по возрастанию. Для каждого продукта храните признак: был ли он уже размещён.
- При первом появлении срока хранения продукт ставится на ближайшее свободное место слева, а при первом появлении срока годности — на ближайшее свободное место справа.
- После обработки каждого числа фиксируйте номер продукта, если он только что получил место, и сам номер занятого места. Последнее такое событие даёт первый ответ, а число занятых мест левее него — второй.
Решение
1. Для каждого продукта создаём две записи: срок хранения с момента изготовления и срок годности после вскрытия. Каждой записи сопоставляем номер продукта и тип срока. 2. Сортируем все записи по возрастанию значения срока. Так как все исходные числа различны, порядок обработки однозначен. 3. Поддерживаем массив рейтинга из N свободных позиций. При обработке первого ещё не использованного срока хранения продукт помещается в первую свободную позицию слева. При обработке срока годности — в первую свободную позицию справа. 4. Когда продукт получает место, запоминаем его номер и позицию. Последний продукт, получивший место, является искомым последним продуктом. 5. Количество продуктов, занявших более высокие места, равно числу уже занятых позиций левее позиции последнего размещённого продукта.
Частые ошибки
- Обрабатывать сначала все сроки хранения, а затем все сроки годности вместо общего сортированного списка.
- Учитывать вторую характеристику уже размещённого продукта.
- Считать более высокими места справа, хотя рейтинг строится слева направо.
- Путать номер продукта с его позицией в рейтинге.
Источник: Открытый банк ФИПИ
Похожие задания
26Отдел маркетинга сети продуктовых магазинов составляет рейтинг продуктов по информации об их сроках хранения…Рейтинг и проходной балл · 623F9126Во время сессии студенты сдают 4 экзамена, за каждый из которых можно получить от 2 до 5 баллов. Студенты…Рейтинг и проходной балл · 7257B426Каждый кандидат в отряд космонавтов проходит 3 испытания, за каждое из которых можно получить от 0 до 100…Рейтинг и проходной балл · EB601E26Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 02861826В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Одну коробку можно…Коробки и коржи: вложение с заданной разностью · 05BFA626Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · 06BC06
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.