В отделении банка работают два окна для обслуживания клиентов. Некоторые услуги могут быть оказаны только при обращении в определённое окно, некоторые — при обращении в любое окно. Клиент входит в отделение и встаёт в очередь к тому окну, которое оказывает необходимую ему услугу. Если услуга может быть оказана в любом окне, клиент выбирает то, в очереди к которому в данный момент меньше людей. Если очереди в оба окна одинаковые, клиент выбирает окно с меньшим номером. При этом если в очереди к выбранному окну уже стоит
Если момент завершения обслуживания одного или нескольких клиентов совпадает с моментом прихода нового клиента, то можно считать, что новый клиент пришёл после того, как обслуживание ранее пришедшего клиента завершилось и очередь сократилась.
Входные данные.
Первая строка входного файла содержит целое
Определите, сколько клиентов будет обслужено в течение дня в окне
В ответе запишите два целых числа: сначала количество клиентов, обслуженных в окне
Ответ:
Приведем решение на языке Python.
f = open('26.txt')
n = int(f.readline())
a = []
for i in f:
prixod, dlitel, N_okna = [int(x) for x in i.split()]
a.append([prixod, dlitel, N_okna])
a.sort()
okno_1 = []
okno_2 = []
count = 0
usli = 0
for prixod, dlitel, N_okna in a:
while len(okno_1) > 0 and okno_1[0] <= prixod:
del okno_1[0]
while len(okno_2) > 0 and okno_2[0] <= prixod:
del okno_2[0]
if N_okna == 1 or (N_okna != 1 and N_okna != 2 and len(okno_1) <= len(okno_2)):
if okno_1 == []:
okno_1.append(prixod + dlitel)
count += 1
elif len(okno_1) < 12:
okno_1.append(okno_1[-1] + dlitel)
count +=1
else:
usli += 1
else:
if okno_2 == []:
okno_2.append(prixod + dlitel)
elif len(okno_2) < 12:
okno_2.append(okno_2[-1] + dlitel)
else:
usli += 1
print(count, usli)
Ответ: 118 467.
Приведём решение Юрия Красильникова на языке Python.
a = sorted([list(map(int,s.split())) for s in open('26.txt')][1:])
q = [0,[],[]] # очереди в окно 1 и окно 2
k = [0]*3 # k[i] - количество обслуженных в окне i (i = 0 - необслуженные)
for x in a:
for i in range(1,3): # удаляем уже обслуженных
while q[i] and q[i][0] <= x[0]:
del q[i][0]
w = x[2] if x[2] > 0 else (1 if len(q[1]) <= len(q[2]) else 2) # выбираем окно
if len(q[w]) >= 12: k[0] += 1 # клиент уходит
else: # клиент становится в очередь
t = q[w][-1] if q[w] else x[0] # время, когда клиента начнут обслуживать
q[w].append(t + x[1]) # время, когда клиент уйдёт
k[w] += 1 # количество клиентов, обслуженных в окне
print(k[1],k[0])