====== Вариант 5.3. Связанные заметки с отменой изменений ======
[[:courses:algorithms_structures:cw_2026:grade5:start|Все варианты на «Отлично»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]]
Уровень: **Отлично**.
===== Постановка задачи =====
Запись — заметка, text — токен её содержимого, tag — тематическая метка. Ссылка a→b означает ссылку из заметки a на заметку b.
Разработайте хранилище записей с текстами, тегами, направленными ссылками и отменой изменений. По тегу нужно быстро находить записи, а по записи — источники входящих ссылок. Удаление записи и его отмена должны сохранять согласованность всех отношений.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
===== Данные и начальное состояние =====
* ''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.3, 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.3, 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.3, 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.3, created by Ivan Ivanov.
Error: EMPTY
OK
OK
OK
OK
ITEMS 1
1
Error: NOT_FOUND
VALUE first