Задание №4563. Файл, необходимый для выполнения задания: ссылка для скачивания. Входной файл содержит заявки пассажиров, желающих сдать свой багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 1 мин. Багаж можно поместить в только что освобождённую ячейку начиная со следующей минуты. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит. Определите, сколько пассажиров сможет сдать свой багаж в течение 24 ч и какой номер будет иметь ячейка, которую займут последней. Если таких ячеек несколько, укажите минимальный номер ячейки. Входные данные. В первой строке входного файла находится натуральное число K, не превышающее 1000, – количество ячеек в камере хранения. Во второй строке – натуральное число N (N ≤ 1000), обозначающее количество пассажиров. Каждая из следующих N строк содержит два натуральных числа, каждое из которых не превышает 1440: указанное в заявке время размещения багажа в ячейке и время освобождения ячейки (в минутах от начала суток). Запишите в ответе два числа: количество пассажиров, которые смогут воспользоваться камерой хранения, и номер последней занятой ячейки. Типовой пример организации данных во входном файле. 2 5 30 60 40 1000 59 60 61 1000 1010 1440 При таких исходных данных положить вещи в камеру хранения смогут первый, второй, четвёртый и пятый пассажиры. Последний пассажир положит вещи в ячейку 1, так как ячейки 1 и 2 будут свободны. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файла.

Задание №4563.
Обработка целочисленной информации. ЕГЭ по информатике

Файл, необходимый для выполнения задания: ссылка для скачивания.

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

Багаж одного пассажира размещается в одной свободной ячейке с минимальным номером. Ячейки пронумерованы начиная с единицы. Размещение багажа в ячейке или её освобождение происходит в течение 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)

Таким образом, 389 пассажира смогут воспользоваться камерой хранения; 133 — номер последней занятой ячейки.

Показать ответ

Источник: ФИПИ. Открытый банк тестовых заданий
Сообщить об ошибке


Тест с похожими заданиями