Задание 26 ЕГЭ по информатике · B3C563
Камера хранения: ячейки и заявкиВысокаяКЭС 3.10
Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки в минутах от начала суток. Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.
В первой строке входного файла находится натуральное число K, не превышающее 1000, — количество ячеек в камере хранения. Во второй строке находится натуральное число N (N ≤ 1000), обозначающее количество пассажиров. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: время размещения багажа в ячейке и время освобождения ячейки. Используйте данные из прилагаемого файла.
1_B3C563.zipВ первой строке входного файла находится натуральное число K, не превышающее 1000, — количество ячеек в камере хранения. Во второй строке находится натуральное число N (N ≤ 1000), обозначающее количество пассажиров. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: время размещения багажа в ячейке и время освобождения ячейки. Используйте данные из прилагаемого файла.
Показать ответ
368 83
Подсказки (3)
- Как можно хранить для каждой ячейки момент времени, начиная с которого она снова доступна?
- Обрабатывайте заявки в порядке их следования. Для каждой заявки найдите ячейку с минимальным номером, для которой время освобождения меньше времени сдачи багажа.
- Если заявка принята в момент t, ячейка становится доступной с момента освобождения плюс 1 минута. Увеличьте число обслуженных пассажиров и обновите максимальный номер занятой ячейки.
Решение
1. Считать количество ячеек K и количество заявок N. Для каждой ячейки сохранить время, с которого она свободна; изначально все ячейки свободны.
2. Для каждой заявки с временем сдачи t и временем освобождения e просмотреть ячейки от первой к последней и выбрать первую ячейку, для которой её время доступности не позже t.
freei≤t
3. Если подходящая ячейка найдена, увеличить счётчик обслуженных пассажиров и установить для неё время следующей доступности e + 1.
freei:=e+1
4. Запомнить наибольший номер ячейки, занятой принятой заявкой. По данным прилагаемого файла вывести количество обслуженных пассажиров и этот номер.
2. Для каждой заявки с временем сдачи t и временем освобождения e просмотреть ячейки от первой к последней и выбрать первую ячейку, для которой её время доступности не позже t.
freei≤t
3. Если подходящая ячейка найдена, увеличить счётчик обслуженных пассажиров и установить для неё время следующей доступности e + 1.
freei:=e+1
4. Запомнить наибольший номер ячейки, занятой принятой заявкой. По данным прилагаемого файла вывести количество обслуженных пассажиров и этот номер.
Частые ошибки
- Освобождать ячейку в ту же минуту, в которую её можно занять.
- Выбирать не первую свободную ячейку, а ячейку с минимальным временем освобождения.
- Продолжать обработку заявки после того, как свободная ячейка не найдена.
- Забывать учитывать номер последней занятой ячейки, если несколько ячеек имеют одинаковый статус.
Источник: Открытый банк ФИПИ
Похожие задания
26Задание выполняется с использованием прилагаемых файлов. Входной файл содержит заявки пассажиров, желающих…Камера хранения: ячейки и заявки · 290F1526Входной файл содержит информацию о заявках граждан, обращающихся в многофункциональный центр (МФЦ) в течение…Камера хранения: ячейки и заявки · 8ECB7C26Входной файл содержит заявки пассажиров, желающих сдать багаж в камеру хранения. В каждой заявке указаны…Камера хранения: ячейки и заявки · A9963526Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2…Игровая стратегия с обоснованием · 02861826В магазине для упаковки подарков есть N кубических коробок из материалов двух видов. Одну коробку можно…Коробки и коржи: вложение с заданной разностью · 05BFA626Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч…Игровая стратегия с обоснованием · 06BC06
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.