====== Вариант 5.7. Каталог ресурсов игрового проекта ====== [[:courses:algorithms_structures:cw_2026:grade5:start|Все варианты на «Отлично»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]] Уровень: **Отлично**. ===== Постановка задачи ===== Каталог — группа ресурсов игрового проекта, файл — ресурс, text — токен его метаданных. Бинарные данные ресурсов не загружаются. Разработайте модель иерархического хранилища в оперативной памяти. В нём есть каталоги и файлы с небольшим текстовым содержимым. Необходимо создавать, искать, удалять и перемещать объекты. Работа с настоящими файлами операционной системы не требуется. Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат. ===== Данные и начальное состояние ===== * ''path'', ''src'', ''dst'' — абсолютные пути: ''/'' либо ''/name/.../name''. Компоненты соответствуют общему формату токена. * Пустые компоненты, повторные разделители, завершающий разделитель (кроме корня), компоненты . и .. запрещены: ''Error: INPUT''. * Длина пути в команде не более 1024 символов; глубина не более 64 компонентов. Превышение длины — INPUT, глубины — RANGE. Допустимые сценарии гарантируют, что после успешного перемещения полные пути всех объектов также остаются в этих пределах; отдельная ошибка для нарушения этой гарантии не требуется. * ''text'' — непустой токен содержимого. Сумма длин имён и содержимого текущих объектов не более 10000000. * Корневой каталог ''/'' существует с начала запуска. Других объектов первоначально нет. Общий предел числа объектов включает корень. ===== Операции ===== ^ Команда ^ Действие ^ Ответ ^ | ''MKDIR path'' | Создать каталог по полному пути; родитель должен существовать и быть каталогом. | OK; занятый путь — Error: EXISTS | | ''PUT path text'' | Создать файл либо заменить содержимое файла. Родитель должен существовать и быть каталогом. | OK; если по пути каталог, Error: STATE | | ''GET path'' | Прочитать файл. | VALUE text; объект отсутствует — NONE; это каталог — Error: STATE | | ''LS path'' | Получить непосредственных детей каталога по возрастанию их имён. | ITEMS k, затем строки D name для каталогов или F name для файлов; файл — Error: STATE | | ''RM path'' | Удалить объект и всё его содержимое, включая вложенные каталоги. | OK | | ''MV src dst'' | Переместить объект src по новому полному пути dst, в том числе переименовать. Родитель dst должен существовать; dst должен быть свободен. | OK; занятый dst — Error: EXISTS | | ''FIND name'' | Найти все файлы и каталоги с точным именем name во всём хранилище, кроме корня. | ITEMS k, затем полные пути лексикографически | ===== Правила выполнения и ошибки ===== Для LS/RM/MV отсутствие обязательного объекта либо родителя возвращает NOT_FOUND; для MKDIR/PUT — отсутствие родителя также NOT_FOUND. Если путь проходит через файл, а не каталог, возвращается STATE; GET для такого пути возвращает STATE, а не NONE. GET возвращает NONE только если при корректном проходе недостаёт компонента. RM и MV корня возвращают STATE. Перемещение каталога в самого себя или своего потомка запрещено. При ''MV /a /a'' существующий dst даёт EXISTS; для свободного dst внутри src — STATE. Предварительно проверяются src и родитель dst слева направо, затем занятость dst, затем запрет перемещения внутрь себя. Корень является своим существующим родителем только для проверки PUT/MKDIR по пути /; MKDIR / даёт EXISTS, PUT / text — STATE. LS упорядочивает файлы и каталоги вместе по ASCII-именам, без группировки по типу; сам запрошенный каталог не выводится. FIND сравнивает точное имя последнего компонента пути, а не подстроку полного пути. Файлы и каталоги одного родителя не могут иметь одинаковые имена. FIND и LS не изменяют данные. Содержимое и потомки при MV сохраняются. Неудачное перемещение ничего не меняет. Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы. ===== Требования к эффективности ===== Пусть h — число компонентов пути, s — максимальное число детей одного каталога, L — максимальная длина компоненты. Поиск по пути, MKDIR, PUT и GET — не хуже O(h·L·log(s+2)); LS допускает дополнительно O(k·L·log(k+2)) для вывода. Для MV допускается O(h·L·log(s+2) + rL), где r — число перемещаемых объектов; RM — O(h·L·log(s+2) + rL). FIND допускает полный просмотр и сортировку найденных путей. Память пропорциональна числу объектов и суммарной длине их данных; все полные пути можно формировать при выводе. Решение не должно при обычном поиске пути перебирать всё хранилище. В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях. ===== Формат ввода и вывода ===== Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта: Course work for option 5.7, created by Ivan Ivanov. Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием. ===== Примеры ===== ==== Пример 1. Создание, перенос и поиск ==== Ввод: 1 7 MKDIR /a PUT /a/x hello MKDIR /b MV /a/x /b/y LS /b GET /b/y FIND y Вывод: Course work for option 5.7, created by Ivan Ivanov. OK OK OK OK ITEMS 1 F y VALUE hello ITEMS 1 /b/y ==== Пример 2. Рекурсивное удаление ==== Ввод: 1 6 MKDIR /a MKDIR /a/b PUT /a/b/x data RM /a LS / GET /a/b/x Вывод: Course work for option 5.7, created by Ivan Ivanov. OK OK OK OK ITEMS 0 NONE ==== Пример 3. Неудачное перемещение сохраняет объекты ==== Ввод: 1 6 MKDIR /a PUT /a/x data MV /a /a/sub GET /a/x RM / LS /a Вывод: Course work for option 5.7, created by Ivan Ivanov. OK OK Error: STATE VALUE data Error: STATE ITEMS 1 F x