Моделирование процесса

«Пассажир кладёт багаж в свободную ячейку с наименьшим номером, а если свободных нет — уходит». Можно ли отказать раннему пассажиру, чтобы потом принять больше?

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

Это принципиальное различие. В первом случае ты сам выбираешь действия:

Найди максимальное количество непересекающихся мероприятий.

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

Клиенты приходят по времени. Каждый занимает свободное окно с наименьшим номером. Если свободных окон нет, клиент уходит.

Воспроизведение такого процесса в программе называют моделированием или симуляцией.

При моделировании нужно хранить состояние системы — сведения о том, что происходит сейчас. Например, free_at = [100, 140, 90] может означать, что первое окно освободится в момент 100, второе — в момент 140, третье — в момент 90. По этому состоянию программа решает, куда направить следующего клиента. Перед поиском алгоритма спрашивай:

Мне разрешено выбирать лучший вариант или я обязан выполнить конкретную процедуру?

Две ячейки, заявки (1, 5), (2, 4), (3, 7), (4, 8), (5, 6), (6, 9): время сдачи и время освобождения. Багаж кладут в свободную ячейку с наименьшим номером, освободившуюся ячейку можно занять со следующей минуты. Как это смоделировать?

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

Состояние — free_at = [0] * k: free_at[i] — минута, в которую освободится ячейка с индексом i. «Со следующей минуты» — значит, ячейка свободна, если free_at[i] < start:

k = 2requests = [(4, 8), (1, 5), (6, 9), (5, 6), (2, 4), (3, 7)]requests.sort()free_at = [0] * kaccepted = 0last_cell = 0for start, finish in requests:    for i in range(k):        if free_at[i] < start:            free_at[i] = finish            accepted += 1            last_cell = i + 1            breakprint(accepted, last_cell)

Те же заявки на шкале времени:

i + 1 — потому что индексы начинаются с нуля, а номера ячеек с единицы. Ячейки проверяются по возрастанию номеров, поэтому первая подходящая — с наименьшим номером, а break не даёт одной заявке занять две ячейки.

Одно слово условия меняет ответ. Если ячейку можно занять в ту же минуту, проверка — free_at[i] <= start, и заявка (4, 8) уже получит ячейку 2: принятых станет пять. А если в файле дана длительность, а не время освобождения, считаем finish = start + duration.

Вернёмся к задаче темы:

«Входной файл 26-12.txt содержит заявки пассажиров, которые сдают багаж в камеру хранения. В заявке указаны время сдачи багажа и время освобождения ячейки (в минутах от начала суток). Ячейки пронумерованы начиная с 1. Багаж кладут в свободную ячейку с наименьшим номером; освободившуюся ячейку можно занять, начиная со следующей минуты после её освобождения. Если свободных ячеек нет, пассажир уходит. В первой строке файла — количество ячеек K, во второй — количество пассажиров N, в каждой из следующих N строк — время сдачи и время освобождения. Определите, сколько пассажиров сдадут багаж, и номер ячейки, в которую положит багаж последний из них.»

Это та же камера хранения: прочитать файл, как в подтеме 1, отсортировать заявки по времени сдачи и исполнить правила. Меняются только число ячеек и количество заявок.

with open('26-12.txt') as f:    k = int(f.readline())    n = int(f.readline())    requests = [tuple(map(int, f.readline().split()))                for i in range(n)] requests.sort()free_at = [0] * kaccepted = 0last_cell = 0for start, finish in requests:    for i in range(k):        if free_at[i] < start:            free_at[i] = finish            accepted += 1            last_cell = i + 1            breakprint(accepted, last_cell)

Ответ: 859 11. 141 пассажир не нашёл свободной ячейки, а последний принятый положил багаж в ячейку 11.

Проверь себя на одном слове условия: с проверкой free_at[i] <= start — «можно в ту же минуту» — программа выведет 877 7. Ячейки освобождаются на минуту раньше, и мест хватает большему числу пассажиров. Поэтому правило освобождения всегда переводят в код дословно.

А если ячейки стоят по-разному и пассажир выбирает самую дешёвую свободную?

Просматривать ячейки не по номеру, а в порядке «цена, номер»; этот порядок вычисляют один раз сортировкой.

Среди равных по цене выбирают ячейку с наименьшим номером. Порядок просмотра ячеек от этого не меняется со временем, поэтому его вычисляют один раз — сортировкой номеров ячеек по ключу (цена, номер):

cost = [50, 30, 30]requests = [(1, 5), (2, 3), (3, 4), (5, 2), (6, 4)]order = sorted(range(len(cost)), key=lambda i: (cost[i], i))free_at = [0] * len(cost)total = 0last_cell = Nonefor start, duration in requests:    for i in order:        if free_at[i] <= start:            free_at[i] = start + duration            total += cost[i]            last_cell = i + 1            breakprint(total, last_cell)

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

На парковке места двух видов, и легковая машина может встать на место микроавтобуса, а наоборот — нет. Как это учесть?

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

Легковая машина проверяет сначала свой список, затем чужой, а микроавтобус — только свой:

spots = {"A": [0], "B": [0]}cars = [(0, 10, "A"), (2, 5, "A"), (3, 4, "B"), (8, 2, "A")]parked_a = gone = 0for arrival, duration, kind in cars:    allowed = ["A", "B"] if kind == "A" else ["B"]    placed = False    for group in allowed:        lst = spots[group]        for i in range(len(lst)):            if lst[i] <= arrival:                lst[i] = arrival + duration                placed = True                break        if placed:            break    parked_a += placed and kind == "A"    gone += not placedprint(parked_a, gone)

Вторая легковая машина встала на место микроавтобуса, поэтому микроавтобус в момент 3 уехал. К моменту 8 место микроавтобуса освободилось, и его заняла третья легковая.

А если свободного окна нет, но клиент готов подождать?

Клиент начинает, когда освободится окно, но не раньше прихода: start = max(arrival, free_at).

Для одного окна достаточно хранить время его освобождения free_at. Клиент пришёл в arrival, обслуживание длится duration, окно свободно с free_at. Тогда start = max(arrival, free_at) и finish = start + duration.

Почему максимум? Обслуживание не может начаться ни раньше прихода клиента, ни раньше освобождения окна. Время ожидания — start − arrival. Если клиент согласен ждать не более max_wait, пройди обслуживание по шагам:

clients = [(0, 5), (2, 3), (4, 4), (12, 2)]max_wait = 3free_at = 0served = rejected = 0for arrival, duration in clients:    start = max(arrival, free_at)    if start - arrival <= max_wait:        free_at = start + duration        served += 1    else:        rejected += 1print(served, rejected)

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

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

Программа повторяет рисунок. В момент прихода сначала снимаем с начала очереди тех, кто уже закончил: их время окончания не больше момента прихода. Оставшиеся — люди в очереди, включая того, кого обслуживают. Новый клиент начнёт, когда закончит последний из них, queue[-1], а если очередь пуста — сразу:

from collections import deque clients = [(0, 4), (1, 3), (2, 5), (9, 2)]queue = deque()for arrival, duration in clients:    while queue and queue[0] <= arrival:        queue.popleft()    people = len(queue)    start = max(arrival, queue[-1]) if queue else arrival    queue.append(start + duration)    print(arrival, people, start)

Каждый клиент видит people — сколько людей перед ним ещё не закончили, — и начинает после последнего из них. Если условие считает длиной очереди только ожидающих, без обслуживаемого клиента, подсчёт нужно изменить.

Для нескольких очередей важно, что именно минимизирует клиент: количество людей, ожидаемое время, номер окна или стоимость услуги. Это разные правила: в первой очереди может стоять один человек, которому осталось 30 минут, а во второй — два человека, каждому нужна одна минута.

Для задач об очередях отдельно выписывай:

1. Кто учитывается в очереди?
2. Как выбирается окно?
3. Как разрешается равенство?
4. Когда клиент отказывается?
5. Учитываются начавшие обслуживание до закрытия или закончившие до закрытия?

«Заполнять контейнер грузами по убыванию массы; не помещается — пробовать следующие». Это лучший способ упаковки?

Не обязательно — но если условие предписывает процедуру, её выполняют буквально и получают именно её результат.

Это процедура, которую нужно воспроизвести:

weights = [7, 6, 4, 3]capacity = 10remaining = sorted(weights, reverse=True)loads = []while remaining:    next_remaining = []    load = 0    for weight in remaining:        if load + weight <= capacity:            load += weight        else:            next_remaining.append(weight)    loads.append(load)    remaining = next_remainingprint(loads)

remaining — грузы, ещё не размещённые; load — загрузка текущего контейнера; next_remaining — грузы для следующих контейнеров; loads — загрузки готовых контейнеров. В первый контейнер 7 помещается, 6 и 4 — нет, 3 — помещается. Предполагается, что каждый отдельный груз не тяжелее контейнера, иначе цикл никогда не завершится.

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

Важно: эта процедура не всегда даёт минимальное число контейнеров. Для вместимости 10 и грузов 6, 5, 3, 2, 2, 2 она даст три контейнера — 6 + 3 = 9, 5 + 2 + 2 = 9 и 2, — а существует размещение в два: 6 + 2 + 2 = 10 и 5 + 3 + 2 = 10. Поэтому нельзя называть результат такого алгоритма оптимальным без доказательства. Если же он прямо предписан условием, нужно получить именно результат предписанной процедуры.

Детали кладут в первый подходящий контейнер, изделия раскладывают с двух концов ленты. Как программировать такие необычные правила?

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

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

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

room = [10, 6, 8]parts = [5, 7, 4, 6, 3]placed = []for part in parts:    for i in range(len(room)):        if room[i] >= part:            room[i] -= part            placed.append(part)            breakprint(len(placed), max(placed), room)

Деталь 7 не помещается в контейнеры 1 и 2 и попадает в третий; для последней детали 3 места не осталось нигде.

Размещение с двух концов. У каждого изделия два времени, например шлифовки и покраски. Все 2N чисел упорядочивают по возрастанию; если очередное наименьшее число — время шлифовки, изделие ставят на первое свободное место от начала ленты, если покраски — на первое свободное место от конца; числа уже размещённых изделий пропускают:

items = [(3, 8), (7, 1), (2, 5), (9, 6)]values = sorted((v, kind, i)                for i, pair in enumerate(items)                for kind, v in enumerate(pair))line = [None] * len(items)front, back = 0, len(items) - 1order = []for v, kind, i in values:    if i + 1 in line:        continue    if kind == 0:        line[front] = i + 1        front += 1    else:        line[back] = i + 1        back -= 1    order.append(i + 1)print(order, line)

Наименьшее число 1 — покраска изделия 2: оно встаёт в конец. Затем 2 — шлифовка изделия 3, оно встаёт в начало. Последним размещено изделие 4; перед ним на ленте два изделия, после него — одно. Каждая запись (значение, вид, номер) хранит, откуда взято число, — это та же связь полей, что и в первой подтеме.

Сервер копит запросы и делает резервную копию, когда память переполняется. С чего начать?

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

Пусть запись журнала содержит время, ID клиента и объём. Сервер накапливает данные; если очередной запрос не помещается в память, сервер создаёт резервную копию уже накопленного, очищает память и добавляет новый запрос. Понадобятся перевод времени, сортировка записей, накопление объёмов по клиентам и моделирование памяти.

Время вида 11:59:59 переводят в секунды: hours, minutes, seconds = map(int, time_text.split(":")) и hours * 3600 + minutes * 60 + seconds — split(":") разбивает строку по двоеточиям. Сравнивать строки времени тоже можно, если у всех две цифры в часах, но секунды надёжнее.

log = [("08:00:05", 7, 40), ("07:59:59", 3, 50),       ("09:10:00", 7, 30), ("11:30:00", 3, 60),       ("12:00:00", 5, 70), ("13:15:00", 7, 20)]capacity = 100records = []for text, client, volume in log:    h, m, s = map(int, text.split(":"))    records.append((h * 3600 + m * 60 + s, client, volume))records.sort() client_total = {}used = 0backups = []for time, client, volume in records:    client_total[client] = client_total.get(client, 0) + volume    if used + volume > capacity:        backups.append((time, used))        used = 0    used += volumebest = max(client_total, key=client_total.get)print(best, *[u for t, u in backups if t < 12 * 3600])

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

Почему условие строгое, used + volume > capacity? При точном заполнении памяти места пока хватает. Почему нельзя автоматически добавить резервную копию в конце программы? Завершение входного файла само по себе не означает, что сервер выполнял копирование. Здесь вторая копия создана ровно в 12:00:00, и условие «до полудня» её не берёт, а «не позднее 12:00:00» — взяло бы: смысл границы берут из условия.

Также различай две крупнейшие копии среди всех подходящих и две соседние по времени копии с максимальной суммой. Для первого случая достаточно выбрать два максимальных объёма, для второго проверяют соседние записи в хронологическом порядке.

• Выбрать или исполнитьправила условия выполняют буквально
• Состояниеfree_at — когда освободится каждая ячейка
• Со следующей минутыfree_at[i] < start
• Задача темы859 11
• Очередьstart = max(arrival, free_at)
• Процедурашаг за шагом, даже если она не лучшая