Инструменты пользователя

Инструменты сайта


courses:algorithms_structures:cw_2026:grade5:3

Вариант 5.3. Связанные заметки с отменой изменений

Постановка задачи

Запись — заметка, 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
courses/algorithms_structures/cw_2026/grade5/3.txt · Последнее изменение: — 127.0.0.1