====== Вариант 5.11. Внутренняя база знаний ====== [[:courses:algorithms_structures:cw_2026:grade5:start|Все варианты на «Отлично»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]] Уровень: **Отлично**. ===== Постановка задачи ===== Запись — статья базы знаний, text — токен содержимого, tag — рубрика. Необходимо получать статьи рубрики, обратные ссылки и отменять изменения. Разработайте хранилище записей с текстами, тегами, направленными ссылками и отменой изменений. По тегу нужно быстро находить записи, а по записи — источники входящих ссылок. Удаление записи и его отмена должны сохранять согласованность всех отношений. Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат. ===== Данные и начальное состояние ===== * ''id'', ''a'', ''b'' — числовые идентификаторы от 1 до 1000000000. * ''text'', ''tag'' — токены общего формата. * Начальное состояние пустое, история изменений пуста. * Одновременно не более 100000 записей, 100000 назначений тегов и 100000 ссылок. Суммарное число сохраняемых в истории описаний тегов и ссылок не более 200000; входные сценарии удовлетворяют этому ограничению. ===== Операции ===== ^ Команда ^ Действие ^ Ответ ^ | ''CREATE id text'' | Создать запись без тегов и ссылок. | OK; id занят — Error: EXISTS | | ''EDIT id text'' | Заменить текст существующей записи. | OK | | ''TAG id tag'' | Добавить тег. Повторное добавление разрешено и не дублирует тег. | OK | | ''UNTAG id tag'' | Удалить тег. Отсутствующий тег существующей записи не является ошибкой. | OK | | ''LINK a b'' | Добавить направленную ссылку a→b. Повторное добавление не дублирует ссылку. | OK | | ''UNLINK a b'' | Удалить ссылку a→b. Отсутствующая ссылка между существующими записями не является ошибкой. | OK | | ''DELETE id'' | Удалить запись, все её теги и все входящие/исходящие ссылки. | OK | | ''GET id'' | Получить текст. | VALUE text; при отсутствии записи NONE | | ''BYTAG tag'' | Получить записи с точным тегом по возрастанию числового id. | ITEMS k, затем k строк id | | ''BACKLINKS id'' | Получить источники ссылок на существующую запись по возрастанию числового id. | ITEMS k, затем k строк id | | ''UNDO'' | Отменить последнюю ещё не отменённую успешную изменяющую команду. | OK; если такой команды нет, Error: EMPTY | ===== Правила выполнения и ошибки ===== Все обязательные записи должны существовать, иначе NOT_FOUND; для LINK/UNLINK сначала проверяется a, затем b. GET — исключение, указанное в таблице. Самоссылки разрешены и считаются одной ссылкой. Для отсутствующего тега BYTAG возвращает ITEMS 0; BACKLINKS отсутствующей записи даёт NOT_FOUND, а существующей записи без входящих ссылок — ITEMS 0. CREATE/EDIT/TAG/UNTAG/LINK/UNLINK/DELETE создают одно событие отмены при каждом успешном выполнении, даже если значение фактически не изменилось. Ошибочные команды и чтение событий отмены не создают. UNDO не записывает новое событие. Последовательные UNDO отменяют предшествующие успешные изменения в обратном порядке. Возвращать отменённое изменение отдельной командой не требуется. UNDO DELETE восстанавливает текст, теги и все направления ссылок; UNDO CREATE удаляет созданную запись. После отмены можно выполнять новые команды; отменённые события больше не доступны. Новые команды, выполненные после отмены, отменяются раньше более старых оставшихся событий. Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы. ===== Требования к эффективности ===== В оценках этого варианта n — суммарное число записей, назначений тегов и ссылок в текущем состоянии. Поиск точной записи и EDIT — ожидаемо O(L) либо гарантированно O(L·log(n+2)); обычный полный просмотр всех записей недопустим. BYTAG/BACKLINKS — не хуже O(L·log(n+2)+k·log(n+2)) без просмотра всех записей/отношений при малом k. Изменение одного тега/ссылки — не хуже O(L·log(n+2)). DELETE и UNDO могут стоить O((r+1)·L·log(n+2)), где r — число затронутых отношений. Память пропорциональна текущим данным и сохранённой истории; полная копия всего хранилища после каждой команды не допускается. В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях. ===== Формат ввода и вывода ===== Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта: Course work for option 5.11, created by Ivan Ivanov. Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием. ===== Примеры ===== ==== Пример 1. Теги и обратные ссылки ==== Ввод: 1 7 CREATE 1 first CREATE 2 second TAG 1 topic TAG 2 topic LINK 1 2 BYTAG topic BACKLINKS 2 Вывод: Course work for option 5.11, created by Ivan Ivanov. OK OK OK OK OK ITEMS 2 1 2 ITEMS 1 1 ==== Пример 2. Отмена удаления восстанавливает отношения ==== Ввод: 1 9 CREATE 1 first CREATE 2 second TAG 2 topic LINK 1 2 DELETE 2 UNDO GET 2 BACKLINKS 2 BYTAG topic Вывод: Course work for option 5.11, created by Ivan Ivanov. OK OK OK OK OK OK VALUE second ITEMS 1 1 ITEMS 1 2 ==== Пример 3. Повторная операция и ошибка ==== Ввод: 1 8 UNDO CREATE 1 first TAG 1 topic TAG 1 topic UNDO BYTAG topic LINK 1 2 GET 1 Вывод: Course work for option 5.11, created by Ivan Ivanov. Error: EMPTY OK OK OK OK ITEMS 1 1 Error: NOT_FOUND VALUE first