Теория расписаний Автоматизированная система генерации тестов

Твитнуть

Плюсануть

Класснуть

Запинить

Олимпиадный тренинг

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

Экзамены

Жадный алгоритм Двоичное дерево поиска Теория расписаний

Первая сессия обычно доставляет много проблем. Одна из них заключается в том, что студенту нужен по крайней мере целый день, чтобы подготовиться к одному экзамену. В день одного экзамена к другому готовиться невозможно. Но основная проблема заключается в том, что студенты могут начать готовиться к i-му экзамену, не раньше чем за t_i дней до него, иначе они все забудут. Глеб хочет начать готовиться к экзаменам как можно позже, но он собирается все экзамены сдать.

Помогите Глебу выбрать день начала подготовки к экзаменам.

Входные данные
Первая строка выходных данных содержит число экзаменов n (1 ≤ n ≤ 50 000). Следующие строки описывают экзамены. Каждое описание состоит из трех строк. Первая строка – это название экзамена (строка, содержащая только латинские буквы, длиной не более 10). Вторая строка – дата экзамена в формате dd.mm.yyyy. Третья строка содержит величину t_i для этого экзамена (1 ≤ t_i ≤ 100 000). Все экзамены проходят от 01.01.1900 до 31.12.2100. Не забудьте, что високосными считаются годы, которые делятся на 4 и не делятся на 100 или которые делятся на 400.

Выходные данные
Выведите в формате dd.mm.yyyy, когда Глеб самое позднее сможет приступить к подготовке к экзаменам. Если расписание не позволяет подготовиться к каждому из экзаменов, то выведите слово Impossible.

Расписание станков

Теория расписаний

Известный завод ждет реорганизация — его собираются переоборудовать 𝑛 новейшими станками. Перед тем, как эти станки будут установлены, требуется разработать интерфейс для обработки задач на этих станках.
После реорганизации наладчик завода будет распределять поступающие задачи между станками. У каждой задачи есть длительность. У каждого станка есть независимая очередь задач, причем новую задачу можно добавить либо строго в конец этой очереди, либо строго в начало, если это срочная задача.
Станки работают строго в порядке очереди, обрабатывая задачи подряд. Как только станок завершает задачу, он сразу же начинает работу над следующей в очереди, если такая есть. На переключение между задачами время не тратится.
Формально определим время начала работы над задачей как первый момент времени, после которого прогресс по задаче строго увеличится. Так, если в момент времени 𝑡 на свободный станок приходят сначала обычная задача 𝐴 и затем срочная задача 𝑈, временем начала 𝑈 станет 𝑡, а временем начала 𝐴 — момент завершения 𝑈.
Аналогично, время завершения работы над задачей — первый момент времени, когда прогресс по задаче достигает ее длительности. Так, если в момент времени 𝑡 прогресс по задаче 𝐴 достиг ее длительности, и станку поступил запрос на обработку срочной задачи 𝑈, временем завершения 𝐴 все равно будет 𝑡.
Для большего понимания советуем после прочтения условия ознакомиться с иллюстрацией внизу.
Всего поддерживается четыре типа запросов.

Добавить задачу номер 𝑖 длительностью 𝑑 в конец очереди 𝑘-го станка.
Если его очередь до этого была пустой, станок тут же начинает работу над добавленной задачей
Отменить задачу с номером 𝑖. Если эта задача еще не была начата, она удаляется из очереди, а порядок остальных задач в очереди не меняется. Если эта задача уже была начата, работа над ней тут же останавливается, и станок берет в работу следующую задачу из очереди. Если эта задача уже была завершена или такой задачи не было, запрос отмены игнорируется
Добавить срочную задачу с номером 𝑖 длительностью 𝑑 в начало очереди 𝑘-го станка. В этом случае работа над текущей задачей (если она есть) на 𝑘 -м станке приостанавливается с сохранением прогресса, и в работу берется данная срочная задача.
До момента завершения срочной задачи все запросы добавления или отмены новых задач к станку номер 𝑘 игнорируются для экономии ресурсов. Иными словами, если в момент времени 𝑡 поступил запрос добавления срочной задачи, все следующие запросы, поступающие к 𝑘-му станку в моменты времени с 𝑡 включительно до 𝑡 + 𝑑 не включительно будут проигнорированы.
По завершении срочной задачи, если работа над какой-то обычной задачей в очереди была приостановлена, эта задача без задержек возвращается в обработку.
Вывести ожидаемый момент времени завершения работы 𝑘-го станка.
Для станка без задач в очереди «ожидаемым» временем завершения его работы будем считать текущий момент времени.

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

Формат входных данных
В первой строке дано целое число 𝑇 (1 ≤ 𝑇 ≤ 1000) — количество наборов входных данных. В первой строке описания набора входных данных через пробел даны два целых числа 𝑛 и 𝑞 (1 ≤ 𝑛, 𝑞 ≤ 10⁵) —
количество станков и количество запросов. Гарантируется, что сумма 𝑛 и сумма 𝑞 по всем наборам входных данных обе не превосходят 10⁵.
В следующих 𝑞 строках описаны запросы к заводу в одном из следующих форматов:
1. «𝑡 𝑠𝑐ℎ𝑒𝑑𝑢𝑙𝑒 𝑖 (𝑑) 𝑜𝑛 𝑘» — добавить задачу на 𝑘-й станок;
2. «𝑡 𝑐𝑎𝑛𝑐𝑒𝑙 𝑖» — отменить задачу;
3. «𝑡 𝑢𝑟𝑔𝑒𝑛𝑡 𝑖 (𝑑) 𝑜𝑛 𝑘» — добавить срочную задачу на 𝑘-м станке;
4. «𝑡 𝑒𝑥𝑝𝑒𝑐𝑡𝑎𝑡𝑖𝑜𝑛 𝑘» — узнать текущее ожидаемое время завершения работы 𝑘-го станка.
Параметр 𝑡 — момент совершения запроса (целое неотрицательное число от 0 до 10⁹). Для всех запросов выполняется 1 ≤ 𝑘 ≤ 𝑛, 1 ≤ 𝑖 ≤ 109 и 1 ≤ 𝑑 ≤ 10⁹.
Также гарантируется, что номера задач (𝑖) уникальны и не повторяются, а запросы упорядочены по времени, то есть 𝑡 каждого следующего запроса не меньше, чем 𝑡 предыдущего.

Формат выходных данных
Выведите в отдельной строке текущее ожидаемое время работы соответствующего станка после каждого запроса типа «𝑒𝑥𝑝𝑒𝑐𝑡𝑎𝑡𝑖𝑜𝑛».
Затем выведите по строке на каждую задачу, запрос на добавление которой не был проигнорирован. Задачи должны быть упорядочены по возрастанию их номеров. В каждой строке через пробел должны быть выведены три числа: номер задачи, время начала ее обработки и время конца ее обработки (или отмены, если задача была отменена до завершения).
Для задач, которые были отменены до начала работы над ними, считайте время начала равным времени первого запроса их отмены.

Замечание
В первом примере из условия обе задачи будут обработаны по расписанию: с 0 до 10 и с 4 до 7 соответственно.
Во втором примере:
1. первая задача должна обрабатываться на первом станке в период [0, 5];
2. вторая задача должна обрабатываться на втором станке в период [0, 5];
3. в момент времени 2 срочная задача номер 3 добавляется на первый станок; она будет обрабатываться в период [2, 7];
4. в момент времени 6 первому станку нужно еще 4 единицы времени на завершение задач 4 и 1; второй станок завершил работу в момент времени 5, а третий станок вообще не начинал работу — для них время ожидания до завершения работы равно 0.

Подробная иллюстрация к третьему примеру приведена ниже. Здесь синим обозначен прогресс по задачам, зеленым — завершенные задачи, красным — отмененные, а градиентом — срочные. Все интервалы короче 1 единицы времени (см. отмененную задачу 3) стоит воспринимать как интервалы длительностью 0.

Train Scheduling

Жадный алгоритм Теория расписаний Задачи на моделирование

**Замечание: Ограничение по памяти для этой задачи 512MB, в два раза больше значения по умолчанию.**

Беси приняли на новую работу - диспетчером поездов. Имеется две железнодорожные станции $A$ и $B$. В связи с ограничением бюджета, эти станции соединены только одной дорогой. Если поезд отправляется от одной станции в момент времени $t$, тогда он прибудет на другую станцию в момент времени $t+T$ ($1\le T\le 10^{12}$).

Имеется $N$ ($1\le N\le 5000$) поездов для которых нужно установить время отправки. $i$-ый поезд должен покинуть станцию $s_i$ в момент времени $t_i или позже ($s_i\in \{A, B\}, 0\le t_i\le 10^{12}$). Запрещено иметь поезда, которые движутся в противоположных направлениях в один и тот же момент времени (поскольку они столкнутся). Однако разрешено иметь множество поездов, которые еду в одном направлении в одно и то же время (предполагаем, что поезда имеют пренебрежимо малые размеры)

Помогите Беси спланрировать времена отправления так, чтобы не было столкновений, а общая задержка была минимальной. Если поезд спланирован на убытие в момент времени $a_i\ge t_i$, общая задержка определяется как $\sum_{i=1}^N(a_i-t_i)$.

ФОРМАТ ВВОДА (с клавиатуры):

Первая строка содержит $N$ и $T$.

Затем следуют $N$ строк, где i-ая строка содержит станции $s_i$ и время $t_i$, соответствующие $i$-ому поезду.

ФОРМАТ ВЫВОДА (на экран):

Минимально возможная общая задержка всех корректных планирований.

Городские центральные диаметры

Теория расписаний Сортировка событий

В одном большом городе готовятся к открытию новой ветки наземного метро. Она пролегает между двумя городами в пригороде по разные стороны от самого города, но проходя через него насквозь. Такую модель наземного метро назвали Городские центральные диаметры (ГЦД).

В рамках подготовки к запуску ГЦД было разработано специальное расписание, содержащее n рейсов в одном направлении и m рейсов в обратном. Для каждого рейса определены a_i - время отправления с первой конечной станции и b_i - время прибытия на вторую конечную станцию, для обратных рейсов c_j - время отправления со второй станции и d_j - время прибытия на первую станцию. Времена измеряются в минутах от начала дня. Внутри большого города поезда могут
передвигаться по различным маршрутам, поэтому поезд, отправившийся позже какого-то другого поезда, может прибыть раньше него.

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

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

Формат входных данных
Первая строка входных данных содержит максимальное время задержки при выполнении рейса t, 0 <= t <= 10⁹.
Следующая строка содержит число n - количество рейсов в расписании в одну сторону, 0 <= n <= 100. Следующие 2n строк содержат числа a₁, b₁, a₂, b₂, ..., a_n, b_n - время отправления поездов от первой станции и время их прибытия на вторую станцию, 0 <= a_i < b_i <= 10⁹.
Следующая строка содержит число m - количество поездов в расписании в обратную сторону, 0 <= m <= 100. Следующие 2m строк содержат время отправления c_j и прибытия d_j поездов в обратном направлении в аналогичном формате, 0 <= cj < dj <= 10⁹.
Поезда в расписании перечислены в произвольном порядке, не обязательно в порядке возрастания времени.

Формат выходных данных
Программа должна вывести одно целое число - минимальное количество поездов, необходимое для выполнения данного расписания.

Ввод	Вывод
4 2 3 8 5 10 1 11 15	3
1 2 15 18 7 9 2 11 14 1 3	1

Тяжелая, вариант-2

Комбинаторика Теория расписаний

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

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число a_i — номер дня, ранее которого не может быть начато выполнение этой задачи.

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

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

В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.

Следующая строка содержит n натуральных чисел a_i (1 ≤ a_i ≤ n) — для каждой работы номер дня, ранее которого не может быть начато выполнение этой задачи. Числа отделены друг от друга одним пробелом.

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

Выведите одно число — количество различных допустимых расписаний выполнения задач.

Пример входных и выходных данных

Ввод	Вывод
5 2 4 4 2 1	4

Тяжелая, вариант-1

Теория расписаний Комбинаторика

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число a_i — номер дня, не позднее которого эта задача должна быть выполнена.

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

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

В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.

Следующая строка содержит n натуральных чисел a_i (1 ≤ a_i ≤ n) — для каждой работы номер дня, не позднее которого она должна быть выполнена. Числа отделены друг от друга одним пробелом.

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

Выведите одно число — количество различных допустимых расписаний выполнения задач.

Пример входных и выходных данных

Ввод	Вывод
5 2 4 4 2 5	4