Задача #1012
Сортировка
(В. Рыбальченко) В городе открылось тайм кафе. В нем есть К столиков. После каждого клиента столик необходимо убрать, на это уходит 5 минут. Уборка начинается в следующую минуту после того, как уходит гость. Новый клиент может сесть в следующую минуту после завершения уборки. Кафе работает с 7:00 и закрывается в 23:00. Все клиенты должны уйти не позже 23:00. За это время в него приходит N клиентов. (Гарантируется, что они придут не раньше 7:00, а планируют уйти не позже 23:00).
Каждого гостя при входе встречает администратор и подбирает для него стол с минимальным номером. Может случиться так, что несколько людей придет одновременно, тогда администратор в первую очередь подбирает столик для того, кто планирует сидеть меньшее время. В случае если все столы заняты, гость готов подождать не более 10 минут, при этом за столом он пробудет обязательно T минут (T – разница между временем прибытия и отбытия), в этом случае выбирается столик, который освободится раньше всего. Если таких несколько, выбирается с меньшим номером.
Определите, сколько клиентов получится обслужить за время работы кафе и номер столика, за который сядет последний клиент.
Входные данные
На первой строке одно число N – количество гостей, пришедших за день. На второй строке одно число K – количество столиков в кафе. Далее N строк, в каждой из которых указано время, когда клиент пришел и время, до которого он планировал пробыть в кафе (время дано в минутах от начала дня).
На первой строке одно число N – количество гостей, пришедших за день. На второй строке одно число K – количество столиков в кафе. Далее N строк, в каждой из которых указано время, когда клиент пришел и время, до которого он планировал пробыть в кафе (время дано в минутах от начала дня).
Типовой пример организации данных:
6
2
10 20 # садится за первый стол
12 50 # садится за второй стол
25 43 # ждет 1 минут и садится за первый стол
38 70 # уходит, так как ближайший стол освободится через 11 минут
40 51 # ждет 10 минут и садится за первый стол
55 70 # уходит, так как не сможет просидеть планируемое время. (ресторан закроется)
Указанный пример для работы ресторана с 00:00 до 01:10. При таких данных кафе сможет обслужить первого, второго, третьего и пятого клиентов. А последний займет столик номер 1.
прим. Стол №1 был занят в промежутках: 10-25; 26-49; 50-66. Стол №2: 12-55.
прим. Стол №1 был занят в промежутках: 10-25; 26-49; 50-66. Стол №2: 12-55.
Войдите, чтобы история ответов и статистика сохранялись.
Решение
Ответ
2496
45