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

Задания

Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения.

В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты.

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

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

В первой строке входного файла находится натуральное число K, не превышающее 1000,  — количество ячеек в камере хранения.

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

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

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

30 60

40 1000

59 60

61 1000

1010 1440

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

Последний пассажир положит вещи в ячейку 1, так как ячейки 1 и 2 будут свободны.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Ответ:

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

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

f = open('1_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)

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

Ответ: 344  53.

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

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

def solve(K, passengers):

lockers = [-1]*K

served_passengers = 0

last_locker = -1

for arrival, departure in sorted(passengers):

for i in range(K):

if lockers[i] < arrival:

lockers[i] = departure

served_passengers += 1

last_locker = i + 1

break

return served_passengers, last_locker

f = open('1_26.txt')

K = int(f.readline())

N = int(f.readline())

passengers = []

for _ in range(N):

arrival, departure = map(int, f.readline().split())

passengers.append((arrival, departure))

print(*solve(K, passengers))

№ п/п	№ задания	Ответ
1	57433	344 53

Ключ