====== Вариант 5.12. Планирование производственных операций ====== [[:courses:algorithms_structures:cw_2026:grade5:start|Все варианты на «Отлично»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]] Уровень: **Отлично**. ===== Постановка задачи ===== Операция — производственный этап, priority — его срочность. Этап b зависит от завершения a, если задано DEP a b. Разработайте планировщик операций с приоритетами и зависимостями. Следующей выбирается самая приоритетная операция, все предпосылки которой выполнены. Зависимости и приоритеты могут меняться во время работы. Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат. ===== Данные и начальное состояние ===== * ''id'', ''a'', ''b'' — числовые идентификаторы от 1 до 1000000000. * ''priority'' — целое число от -1000000000 до 1000000000; большее значение означает более высокий приоритет. * ''k'' — число от 0 до 100000. До 100000 операций и 200000 зависимостей одновременно. * Сначала операций нет. Состояния операции: PENDING (ожидает) и DONE (завершена). ===== Операции ===== ^ Команда ^ Действие ^ Ответ ^ | ''ADD id priority'' | Создать PENDING-операцию без предпосылок. | OK; id занят — Error: EXISTS | | ''PRIORITY id priority'' | Изменить приоритет PENDING-операции. | OK; для DONE — Error: STATE | | ''DEP a b'' | Добавить предпосылку: b может завершиться только после a. Обе операции должны быть PENDING. | OK; цикл или DONE-участник — Error: STATE | | ''NEXT'' | Получить лучшую готовую операцию без изменения её состояния. | VALUE id priority; если готовых нет, NONE | | ''DONE id'' | Завершить готовую PENDING-операцию. | OK; если не готова или уже DONE, Error: STATE | | ''CANCEL id'' | Удалить операцию и все её входящие/исходящие зависимости. | OK | | ''READY k'' | Выдать первые min(k,r) готовых операций, где r — их число. | ITEMS m, затем m строк id priority | ===== Правила выполнения и ошибки ===== Операция готова, если она PENDING и все её существующие предшественники DONE. Из готовых выбирается наибольший приоритет, при равенстве — наименьший числовой id. Тот же порядок используется в READY. NEXT/READY не начинают и не завершают операции. Отсутствующий обязательный id — NOT_FOUND, для DEP проверяются a и b слева направо. Зависимость операции от самой себя или любая зависимость, создающая цикл, запрещены. Повтор DEP для двух PENDING-операций успешен без дублирования. Завершённые операции сохраняются и продолжают удовлетворять уже существующим зависимостям, но новые зависимости с их участием запрещены. CANCEL разрешён и для DONE; удалённая предпосылка больше не блокирует зависимые операции. Удалённый id разрешено использовать снова, но новая операция не получает старых зависимостей. Неудачный DEP не меняет готовность операций. Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы. ===== Требования к эффективности ===== В этих оценках n — число всех сохранённых операций, включая DONE, m — число текущих зависимостей. NEXT — O(1). ADD/PRIORITY — не хуже O(log(n+2)) ожидаемо или гарантированно. DEP допускается за O(n+m) из-за проверки допустимости зависимости. DONE/CANCEL — не хуже O((r+1)·log(n+2)), где r — число затронутых зависимостей. READY допускает O(n+k·log(n+2)) с временными данными. Память — O(n+m). NEXT и PRIORITY не должны каждый раз пересматривать все операции. В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях. ===== Формат ввода и вывода ===== Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта: Course work for option 5.12, created by Ivan Ivanov. Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием. ===== Примеры ===== ==== Пример 1. Завершение предпосылки ==== Ввод: 1 7 ADD 1 5 ADD 2 9 DEP 1 2 NEXT DONE 1 NEXT READY 5 Вывод: Course work for option 5.12, created by Ivan Ivanov. OK OK OK VALUE 1 5 OK VALUE 2 9 ITEMS 1 2 9 ==== Пример 2. Равенство приоритетов и отмена ==== Ввод: 1 6 ADD 2 5 ADD 1 5 NEXT DEP 1 2 CANCEL 1 NEXT Вывод: Course work for option 5.12, created by Ivan Ivanov. OK OK VALUE 1 5 OK OK VALUE 2 5 ==== Пример 3. Цикл и неготовая операция ==== Ввод: 1 6 ADD 1 5 ADD 2 9 DEP 1 2 DEP 2 1 DONE 2 NEXT Вывод: Course work for option 5.12, created by Ivan Ivanov. OK OK OK Error: STATE Error: STATE VALUE 1 5