Решение: Обработка журнала сервера
Сервер выполняет запросы на передачу данных. Сведения о каждом запросе — время регистрации, идентификатор клиента и объём переданных данных — сохраняются в журнале, а сам запрос помещается в специальный раздел памяти сервера ограниченного объёма. Если для очередного запроса недостаточно свободной памяти, сервер создаёт резервную копию всех накопленных данных, освобождает раздел и продолжает выполнение запросов. Обработайте журнал работы сервера и определите наименьший суммарный объём данных, переданных с двух клиентских устройств, при условии, что с каждого устройства передано не менее 150 000 Кбайт, а также наименьший объём резервной копии, выполненной не позднее 11:59:59.
Первая строка входного файла содержит два натуральных числа $N$ и $K$: количество записей в журнале и вместимость специального раздела памяти в Кбайт. Каждая из следующих $N$ строк содержит время регистрации запроса в формате ЧЧ:ММ:СС, идентификатор клиентского устройства $C$ и объём данных запроса $S$ в Кбайт. Записи расположены в хронологическом порядке.
В ответе запишите два числа: сначала наименьший суммарный объём данных с двух клиентских устройств, удовлетворяющих условию, затем наименьший объём резервной копии в Кбайт, выполненной не позднее 11:59:59. Данные для обработки находятся в прилагаемом файле.
Решение по шагам
4 шагаСоздаём таблицу или словарь, где каждому идентификатору клиента соответствует суммарный объём переданных им данных.
$$T_C = \sum S_i$$Из полученных сумм выбираем значения не менее 150 000 Кбайт и находим сумму двух наименьших таких значений.
Для моделирования работы раздела храним текущий объём накопленных данных. Перед добавлением очередного запроса проверяем, помещается ли он в оставшуюся память. Если нет, фиксируем текущий объём как резервную копию, проверяем время копирования и затем начинаем накопление нового раздела с объёма текущего запроса.
$$V + S > K \Rightarrow \text{резервная копия объёма } V$$Среди резервных копий, выполненных до 12:00:00, выбираем минимальный объём.
Значения определяются по данным прилагаемого файла.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Учитывают запрос, вызвавший переполнение, в предыдущей резервной копии.
Сравнивают с 11:59:59 только время последнего запроса, а не время каждой резервной копии.
Выбирают двух клиентов с наименьшими суммами без проверки условия 150 000 Кбайт для каждого.
Сбрасывают текущий объём раздела до нуля, но забывают добавить в новый раздел запрос, вызвавший резервирование.