====== Вариант 5.9. Сохранения состояния игры ======
[[:courses:algorithms_structures:cw_2026:grade5:start|Все варианты на «Отлично»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]]
Уровень: **Отлично**.
===== Постановка задачи =====
key/value — параметр игрового мира и его значение, коммит — сохранение, ветка — альтернативная линия прохождения. Сам игровой процесс и случайность не моделируются.
Разработайте систему версий набора пар «ключ–значение». Пользователь изменяет рабочее состояние, сохраняет неизменяемые снимки, создаёт ветки, переключается между ними и сравнивает версии. Хранение большого числа почти одинаковых снимков должно экономить память.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
===== Данные и начальное состояние =====
* ''key'', ''value'', ''cid'', имена веток и идентификаторы коммитов a/b — токены общего формата.
* Сначала существует пустой коммит ''0'' и единственная ветка ''main'', указывающая на него; main является текущей.
* Рабочее состояние первоначально пустое. Коммит — неизменяемый снимок и идентификатор его родительского коммита.
* В каждом состоянии не более 100000 пар. Все созданные коммиты и ветки сохраняются до завершения сценария.
===== Операции =====
^ Команда ^ Действие ^ Ответ ^
| ''PUT key value'' | Изменить или добавить пару в рабочем состоянии. | OK |
| ''DEL key'' | Удалить пару из рабочего состояния. | OK; при отсутствии Error: NOT_FOUND |
| ''GET key'' | Прочитать рабочее значение. | VALUE value; при отсутствии NONE |
| ''COMMIT cid'' | Создать новый снимок рабочего состояния. Его родитель — текущий коммит; текущая ветка передвигается на cid. | OK; занятый cid — Error: EXISTS |
| ''BRANCH name'' | Создать ветку на текущем коммите, не переключаясь на неё. | OK; занятое имя — Error: EXISTS |
| ''CHECKOUT name'' | Сделать существующую ветку текущей и заменить рабочее состояние её снимком. Несохранённые изменения теряются. | OK; ветка отсутствует — Error: NOT_FOUND |
| ''READ cid key'' | Прочитать значение из существующего снимка. | VALUE value; ключ отсутствует — NONE; коммит отсутствует — Error: NOT_FOUND |
| ''DIFF a b'' | Найти различия снимков a и b, по возрастанию ключа. | ITEMS k, затем ADD key new, DEL key old либо MOD key old new; отсутствующий коммит — Error: NOT_FOUND |
| ''MERGE name'' | Объединить текущую ветку с существующей веткой по описанным ниже правилам. | OK; ветка отсутствует — Error: NOT_FOUND; недопустимое объединение — Error: STATE |
===== Правила выполнения и ошибки =====
Пространства имён коммитов и веток независимы. COMMIT разрешён даже без изменений. BRANCH не сохраняет несохранённые рабочие пары и не переключает ветку. CHECKOUT, в том числе текущей ветки, отбрасывает несохранённые изменения. Родителем нового коммита становится вершина текущей ветки, а не последний по времени коммит другой ветки. Предком считается и сам коммит, и любой коммит, достижимый последовательным переходом к родителю.
MERGE требует, чтобы рабочие пары точно совпадали с текущим снимком; иначе STATE. Сначала проверяется существование целевой ветки. Если текущая вершина — предок целевой, текущая ветка и рабочее состояние заменяются целевой вершиной/снимком. Если целевая вершина — предок текущей, операция успешна без изменений. Если вершины разошлись, возвращается STATE. Нового коммита MERGE не создаёт, другая ветка не изменяется. Объединение произвольных конфликтующих изменений не требуется.
В DIFF направление — от a к b. ADD означает отсутствие ключа в a и наличие в b; DEL — наоборот; MOD — наличие в обоих с разными значениями. Неизменившиеся ключи не выводятся. Изменения рабочего состояния и переключения не меняют ранее сохранённые снимки.
Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.
===== Требования к эффективности =====
Пусть N — максимальное число пар в одном состоянии за сценарий; C — число сохранённых коммитов, включая 0; B — число веток, включая main; L — максимальная длина любого строкового поля. Обозначим M=L·log(C+B+2) — допустимую стоимость доступа к метаданным имён. PUT, DEL, GET — O(L·log(N+2)); READ — O(M+L·log(N+2)). COMMIT, BRANCH и CHECKOUT — O(M), без обхода всех пар. Для DIFF допустимо O(M+(na+nb+1)·L), где na и nb — числа пар в сравниваемых снимках. Для MERGE допустимо O(M+(N+1)·L+C): можно сравнивать рабочие пары и проходить историю. Эти границы относятся к худшему случаю, кроме отдельно оговорённого освобождения памяти.
Пусть U — суммарное число успешных PUT и DEL с начала сценария, включая повторную запись того же значения. При U таких изменениях суммарная память всех версий и рабочего состояния должна быть O((U+1)·L·log(N+2)+(C+B)·L), а не O(C·N·L). Способ повторного использования неизменённых данных выбирает студент. Освобождение уже недоступных данных можно учитывать амортизированно.
В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.
===== Формат ввода и вывода =====
Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:
Course work for option 5.9, created by Ivan Ivanov.
Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.
===== Примеры =====
==== Пример 1. Ветки и продвижение к новой версии ====
Ввод:
1
10
PUT a x
COMMIT c1
BRANCH dev
PUT a y
COMMIT c2
CHECKOUT dev
GET a
MERGE main
GET a
READ c1 a
Вывод:
Course work for option 5.9, created by Ivan Ivanov.
OK
OK
OK
OK
OK
OK
VALUE x
OK
VALUE y
VALUE x
==== Пример 2. Направление сравнения ====
Ввод:
1
7
PUT a x
COMMIT c1
PUT a y
PUT b z
COMMIT c2
DIFF c1 c2
DIFF c2 c1
Вывод:
Course work for option 5.9, created by Ivan Ivanov.
OK
OK
OK
OK
OK
ITEMS 2
MOD a x y
ADD b z
ITEMS 2
MOD a y x
DEL b z
==== Пример 3. Разошедшиеся ветки ====
Ввод:
1
9
BRANCH dev
PUT a x
COMMIT left
CHECKOUT dev
PUT a y
COMMIT right
MERGE main
GET a
READ left a
Вывод:
Course work for option 5.9, created by Ivan Ivanov.
OK
OK
OK
OK
OK
OK
Error: STATE
VALUE y
VALUE x