26.09 Прочие прототипы
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
Источник: https://kpolyakov.spb.ru/
В операционном зале есть N банкоматов, работающих круглосуточно. Все банкоматы пронумерованы. В течение дня M клиентов хотят воспользоваться банкоматом. Клиенты обслуживаются в порядке общей очереди. Если в один момент подошли несколько клиентов, то они становятся в очередь в порядке расположения данных в файле. Клиент, стоящий первым в очереди, подходит к первому освободившемуся банкомату (если таких несколько – к банкомату с наименьшим номером). Обслуживание очередного клиента может начаться в ту же минуту, когда банкомат станет свободным. Известно время в минутах от начала суток, когда клиент подошёл к банкомату, и время его обслуживания.
Определите наименьшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента этим банкоматом. Последним обслуженным клиентом считается тот, который подошёл к банкомату до окончания суток (его обслуживание могло закончиться в следующие сутки).
Входные данные
В первой строке входных данных задается два числа: N - количество банкоматов и M – количество клиентов. В каждой из последующих M строк содержится информация по одному клиенту: время начала обслуживания клиента (в минутах с начала суток) и время обслуживания (в минутах).
Выходные данные
Запишите в ответе два числа: наименьшее количество клиентов, которые были обслужены одним банкоматом за 24 часа, и время начала обслуживания последнего клиента этим банкоматом (если таких несколько – банкомата с наименьшим номером).
Пример входного файла:
При таких исходных данных наименьшее число клиентов (2) обслужит 2-й банкомат: это клиенты со временем обслуживания 12 и 8. Последний из них начинает работу с банкоматом на 18-й минуте. Ответ: 2 18.
Решение 1
with open(’26.txt’) as F: N, M = map( int, F.readline().split() ) data = [] for _ in range(M): t0, delta = map(int, F.readline().split()) data.append( (t0, delta) ) data.sort( key = lambda x: x[0] ) tFree = [0]*N stats = [(0,0)]*N TMAX = 24*60 i = 0 queue = [] for t in range(TMAX): while i < len(data) and data[i][0] <= t: queue.append( data[i][1] ) i += 1 while queue: delta, placed = queue[0], False for k in range(N): if tFree[k] <= t: tFree[k] = t + delta stats[k] = (stats[k][0]+1, t) placed = True queue.pop(0) break if not placed: break print( *min( stats, key = lambda x: x[0] ) )
Решение 2
f = open(’26.txt’) n, m = map(int, f.readline().split()) a = [list(map(int, f.readline().split())) for i in range(m)] a = sorted(a, key = lambda x: x[0]) banks = [-1] * n banks_start = [-1]*n cnt_banks = [0] * n for start, time in a: f = 0 end = start + time for j in range(len(banks)): if start <= 1440: if start >= banks[j]: banks[j] = end cnt_banks[j] += 1 f = 1 banks_start[j] = start break if f == 0: min_t = min(banks) if min_t < 1440: ind = banks.index(min_t) banks[ind] += time banks_start[ind] = min_t cnt_banks[ind] += 1 print(min(cnt_banks), banks_start[cnt_banks.index(min(cnt_banks))])
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
