РЕШУ ЕГЭ — информатика

Задания

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

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

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

Задание 26

Входные данные.

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

Выходные данные.

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

Типовой пример организации данных:

30 1000

60 100

61 1100

1010 1440

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

Ответ:

Решение. Считаем файл в массив и отсортируем его. Будем последовательно заполнять каждую ячейку, проверяя, чтобы время укладки нового багажа отличалось от времени забора багажа предыдущим пассажиром на 1 и более. Также будем запоминать номер последней ячейки, куда был сдан багаж.

Приведём решение на языке Python.

f = open('26.txt')

k = int(f.readline())

n = int(f.readline())

a = sorted([list(map(int, i.split())) for i in f])

count = 0

maxt = kposled = 0

for i in range (1, k+1):

start = 0

for x in a:

if x[0]-start >= 1 and x[0] > 0 and x[1] > 0:

count +=1

start = x[1]

if x[0] >= maxt:

maxt = x[0]

kposled = i

x[0] = -1

x[1] = -1

print(count, kposled)

В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ  — 586 3.

Ответ: 586  3.

Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.

Приведём решение Евгения Джобса (без сортировки, с использованием словаря).

Для наиболее удобного поиска багажа заведем словарь вида «время сдачи»: «времена выдачи». Так как в задаче не указано, что нет багажей, которые сдаются одновременно, необходимо предусмотреть хранение нескольких багажей с одинаковым временем сдачи. При таком изменении мы можем определять есть ли багажи с проверяемым временем сдачи за O(1) с помощью команды time in bags.

from collections import defaultdict

with open('26.txt') as f:

k = int(f.readline())

n = int(f.readline())

bags = defaultdict(list)

for i in range(n):

a, b = map(int, f.readline().split())

bags[a].append(b)

storage = [-1]*(k+1) # хранилище

last = cnt = 0

for time in range(1440): # перебираем минуты

if time in bags: # есть багаж в очереди

for end in bags[time]:

for cell in range(1,k+1):

if storage[cell] == -1:# пустая ячейка

storage[cell], last = end, cell

cnt += 1

break

for cell in range(k):

if storage[cell] == time: # багаж забирают

storage[cell] = -1 # освобождаем ячейку

print(cnt, last)

Приведём решение Анатолия Хачатурова на языке Python.

f = open('26.txt')

k = int(f.readline())

n = int(f.readline())

data = [list(map(int, i.split())) for i in f]

data = sorted(data)

sp = []

for n in range(k):

sp.append([0])

c = 0

spi = []

for r in data:

for place in sp:

if r[0] >= place[0]:

c +=1

place.remove(place[0])

place.append(r[1] + 1)

spi.append(sp.index(place))

break

print(spi[-1] + 1, c)

№ п/п	№ задания	Ответ
1	55822	586 3

Ключ