Задание №4407.
Обработка целочисленной информации. ЕГЭ по информатике
Файл, необходимый для выполнения задания: ссылка для скачивания.Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток).
Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты.
Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки.
Входные данные.В первой строке входного файла находится натуральное число
K, не превышающее 1000, – количество ячеек в камере хранения.
Во второй строке – натуральное число
N (N ≤ 1000), обозначающее количество пассажиров. Каждая из следующих
N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанное в заявке время размещения багажа в ячейке и время освобождения ячейки (в минутах от начала суток).
Запишите в ответе два числа: количество пассажиров, которые смогут воспользоваться камерой хранения, и номер последней занятой ячейки.
Типовой пример организации данных во входном файле.2
5
30 60
40 1000
59 60
61 1000
1010 1440
При таких исходных данных положить вещи в камеру хранения смогут первый, второй, четвёртый и пятый пассажиры. Последний пассажир положит вещи в ячейку 1, так как ячейки 1 и 2 будут свободны.Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файла.
Пояснение:
Решим задание, написав программу на языке программирования Python.
Алгоритм действий следующий: храним данные о клиентах в списке из картежей, где первый элемент картежа — время сдачи багажа, а второй — время освобождения ячейки. Сортируем список по возрастанию по времени сдачи багажа. Создаем список "storage" для хранения информации о занятых и свободных ячейках.
Совершая обход всех заявок при помощи цикла for, вначале проверяем освободились ли ко времени сдачи багажа, указанной в заявке, занятые в хранилище ячейки. Если да, то освобождаем такие ячейки. Затем проверяем, есть ли свободное место в хранилище. Если да, то принимаем багаж для хранения, помещая его в ячейку с минимальным номером.
with open('input.txt') as data:
K = int(data.readline())
N = int(data.readline())
data = sorted([(int(i.split()[0]), int(i.split()[1])) for i in data.read().splitlines()])
storage = [0 for i in range(K)]
count_clients = 0
last_cell_number = 0
for x in range(len(data)):
storage = [i if i != 0 and data[x][0] < i[1]+1 else 0 for i in storage]
if len([i for i in storage if i != 0]) < K:
last_cell_number = storage.index(0) + 1
storage[storage.index(0)] = data[x]
count_clients += 1
print(count_clients, last_cell_number) |
Таким образом,
344 пассажира смогут воспользоваться камерой хранения;
53 — номер последней занятой ячейки.
Показать ответ
344 53|53 344
Источник: ФИПИ. Открытый банк тестовых заданий
Сообщить об ошибке
Тест с похожими заданиями