Все варианты на «Отлично» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Отлично.
Запись — статья базы знаний, text — токен содержимого, tag — рубрика. Необходимо получать статьи рубрики, обратные ссылки и отменять изменения.
Разработайте хранилище записей с текстами, тегами, направленными ссылками и отменой изменений. По тегу нужно быстро находить записи, а по записи — источники входящих ссылок. Удаление записи и его отмена должны сохранять согласованность всех отношений.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
id, a, b — числовые идентификаторы от 1 до 1000000000.text, tag — токены общего формата.| Команда | Действие | Ответ |
|---|---|---|
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 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
Ввод:
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
Ввод:
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