26.06 Распределение объектов по местам (хранение багажа, парковки, кафе, гостиницы)
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
В заведении M есть K столиков и C камер хранения. Заведение работает с 8:00 до 22:00. Клиенты приходят в заведение в определенный период, говорят на какой период времени хотят посетить заведение, а также требуется ли клиенту камеру хранения (0 – не требуется, 1 – требуется). Клиент остается и наслаждается проведенным временем, только в случае если его условия выполнены. Если одновременно пришло несколько людей, то сначала регистрируем того, кто больше проведет в кафе. Следующий клиент может занять столик в следующую минуту после освобождения. Следующий клиент может занять камеру хранения в следующую минуту после освобождения. Освобождение стола длится 6 минут. Освобождение камеры хранения – 2 минуты. Освобождение камеры хранения, стола начинается в следующую минуту после ухода клиента. Нумерация столов и камер хранения начинается с 1. Нужно определить количество человек, которое останется в заведении, а также номер столика, за который сядет последний клиент.
Входные данные: В первой строке записано первое число N – количество клиентов. Во второй строке записаны числа K – количество столиков в заведении и C – количество камер хранения. В последующих строках записано по три неотрицательных числа: время прихода (время от начала суток), время, на которое человек хочет посетить заведение и нужна ли камера хранения клиенту или нет.
Запишите через пробел в ответ два числа: количество клиентов, которое останется в заведении и номер столика, за который сядет последний клиент.
Решение (Python)
file = open(’26_11__3ck6k.txt’) count_client = int(file.readline()) # количество клиентов count_tables,count_cameras = map(int,file.readline().split()) # количество столов и камер array_client = list(list(map(int,i.split())) for i in file) # сортируем клиентов по возрастанию времени прихода и по убыванию времени ухода array_client.sort(key = lambda x:(x[0],-x[1])) count = 0 last = 0 cameras = [-1]*count_cameras # симулируем камеры. В каждой ячейке будет записано время освобождения данной камеры tables = [-1]*count_tables # симулируем столики. В каждой ячейке будет записано время освобождения данного стола for start,duration,needed in array_client: # проход по клиентам # если клиент пришел позже или во время открытия и уйдет не позже закрытия if start >= 8*60 and start + duration <= 22*60: if needed == 0: # если человеку не нужна камера хранения for i in range(len(tables)): # перебор столиков if start > tables[i]: # если время прихода текущего человека больше чем время освобождения столика человеком, который занял данный столик tables[i] = start + duration + 6 # записываем время освобождения данного столика count += 1 last = i + 1 # запоминаем номер столика, за который сел последний клиент break # сбрасываем цикл - переходим к следующему клиенту else: # если человеку нужна камера хранения check = 0 # переменная, по которой мы будем проверять: нашли ли мы для человека стол или нет ind_temp_table = 0 # индекс столика, за который мы сможем посадить человека for i in range(len(tables)): # перебор столиков if start > tables[i]: # если время прихода текущего человека больше чем время освобождения столика человеком, который занял данный столик ind_temp_table = i #сохраняем индекс столика, но пока не сажаем клиента за место check = 1 # увеличиваем переменную для проверки break # сбрасываем цикл перебора столиков if check == 1: #проверка на то,что мы смогли подобрать столик для клиента for i in range(len(cameras)): # перебор камер if start > cameras[i]: # если время прихода текущего человека больше чем время освобождения камеры человеком, который занял данную камеру cameras[i] = start + duration + 2 # записываем время освобождения данной камеры tables[ind_temp_table] = start + duration + 6 # записываем время освобождения данного столика count += 1 last = ind_temp_table + 1 # запоминаем номер столика, за который сел последний клиент break # прерываем цикл - переходим к следующему клиенту print(count,last)
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
