Е26.18 В аэропорту есть камера хранения из K ячеек, которые пронумерованы с 1.

Администратор

3 года назад

В аэропорту есть камера хранения из K ячеек, которые пронумерованы с 1. Принимаемый багаж кладется в свободную ячейку с минимальным номером. Известно время, когда пассажиры сдают и забирают багаж (в минутах с начала суток). Ячейка доступна для багажа, начиная со следующей минуты, после окончания срока хранения. Если свободных ячеек не находится, то багаж не принимается в камеру хранения.

Найдите количество багажей, которое будет сдано в камеры за 24 часа и номер ячейки, в которую сдаст багаж последний пассажир.

Входные данные
В первой строке входного файла находится число K – количество ячеек в камере хранения, во второй строке файла число N – количество пассажиров, сдающих багаж (натуральное число, не превышающее 1000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1440: время сдачи багажа и время выдачи багажа.

Выходные данные
Программа должна вывести два числа: количество сданных в камеру хранения багажей и номер ячейки, в которую примут багаж у последнего пассажира, который сможет сдать багаж.
Типовой пример организации данных:
2
4
30 1000
60 100
61 1100
1010 1440

Для указанного примера багаж смогут сдать первый, второй и четвёртый пассажир. Последний пассажир сдаст свой багаж в ячейку один, так как к этому моменту первая и вторая ячейка будут свободны.

TXT

количество сданных в камеру хранения багажей

номер ячейки, в которую примут багаж у последнего пассажира, который сможет сдать багаж

Досрочный ЕГЭ по информатике 2023 г. Евгений Джобс – задание №26

Показать решение...

Решение:

Решение на Python

f = open('26.txt')
k = int(f.readline())
n = int(f.readline())
a = []
for i in range(n):
    st, end = map(int, f.readline().split())
    a.append([st,end])
count = 0
last = 0
a.sort()
kamera = [[0,0]]*k
for i in range(n):
    for j in range(k):
        if kamera[j][1] < a[i][0]:
            kamera[j] = [0,0]
    free = [j for j in range(k) if kamera[j][0]==0]
    if len(free) > 0:
        count += 1
        last = min(free) + 1
        kamera[min(free)] = a[i]
print(count, last)

f = open('26.txt')

k = int(f.readline())

n = int(f.readline())

a = []

for i in range(n):

st, end = map(int, f.readline().split())

a.append([st,end])

count = 0

last = 0

a.sort()

kamera = [[0,0]]*k

for i in range(n):

for j in range(k):

if kamera[j][1] < a[i][0]:

kamera[j] = [0,0]

free = [j for j in range(k) if kamera[j][0]==0]

if len(free) > 0:

count += 1

last = min(free) + 1

kamera[min(free)] = a[i]

print(count, last)

ИЛИ

Решение — Валеев Амир Ильнарович

k = int(f.readline())
n = int(f.readline())
yach = [list(map(int,s.split())) for s in f.readlines()]
yach.sort()
kam = [0] * k
lst = 0
c = 0
for nach,kon in yach:
    for i in range(len(kam)):
        if nach > kam[i]:
            kam[i] = kon
            lst = i + 1
            c += 1
            break
print(c,lst)

k = int(f.readline())

n = int(f.readline())

yach = [list(map(int,s.split())) for s in f.readlines()]

yach.sort()

kam = [0] * k

lst = 0

c = 0

for nach,kon in yach:

for i in range(len(kam)):

if nach > kam[i]:

kam[i] = kon

lst = i + 1

c += 1

break

print(c,lst)

Ответ: 586 3