====== Вариант 5.8. Версии конфигурации сервиса ====== [[: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.8, 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.8, 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.8, 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.8, created by Ivan Ivanov. OK OK OK OK OK OK Error: STATE VALUE y VALUE x