====== Вариант 4.1. Каталог меню с диапазонными запросами ====== [[:courses:algorithms_structures:cw_2026:grade4:start|Все варианты на «Хорошо»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]] Уровень: **Хорошо**. ===== Постановка задачи ===== name — название блюда, price — цена в копейках. Каталог меню должен поддерживать точный поиск и выборки по названиям. Разработайте каталог именованных позиций с ценами. Помимо точного поиска он должен поддерживать получение наименьшего имени, не меньшего заданного и упорядоченной выборки по диапазону имён. Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат. ===== Данные и начальное состояние ===== * ''name'', ''lo'', ''hi'' — непустые токены по общему формату. * ''price'' — целая цена от 0 до 1000000000 копеек. * Начальное состояние пустое. Имена уникальны. ===== Операции ===== ^ Команда ^ Действие ^ Ответ ^ | ''PUT name price'' | Создать позицию либо заменить цену существующей. | OK | | ''GET name'' | Получить цену. | VALUE price; при отсутствии NONE | | ''DEL name'' | Удалить позицию. | OK; при отсутствии Error: NOT_FOUND | | ''RANGE lo hi'' | Получить позиции с lo ≤ name ≤ hi, по возрастанию имени. | ITEMS k, затем k строк name price; если lo > hi, Error: RANGE | | ''LOWER name'' | Найти наименьшее сохранённое имя, которое не меньше аргумента. | VALUE name price; если такого имени нет, NONE | ===== Правила выполнения и ошибки ===== Границы RANGE включительны. Сравнение имён посимвольное по ASCII с учётом регистра. LOWER сравнивает имена, а не цены. Повторный PUT не создаёт вторую позицию с тем же именем. Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы. ===== Требования к эффективности ===== PUT, GET, DEL, LOWER — O(L·log(n+2)) в худшем случае; RANGE — O(L·log(n+2) + kL). Память — O(nL). Малый диапазон не должен требовать полного просмотра каталога. Гарантии должны выполняться и при вставке уже отсортированных имён. В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях. ===== Формат ввода и вывода ===== Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта: Course work for option 4.1, created by Ivan Ivanov. Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием. ===== Примеры ===== ==== Пример 1. Цены и диапазон ==== Ввод: 1 5 PUT tea 100 PUT soup 300 PUT cake 200 RANGE cake soup LOWER su Вывод: Course work for option 4.1, created by Ivan Ivanov. OK OK OK ITEMS 2 cake 200 soup 300 VALUE tea 100 ==== Пример 2. Обновление и пустая выборка ==== Ввод: 1 5 PUT tea 100 PUT tea 120 GET tea RANGE a b LOWER z Вывод: Course work for option 4.1, created by Ivan Ivanov. OK OK VALUE 120 ITEMS 0 NONE ==== Пример 3. Неверный диапазон ==== Ввод: 1 4 PUT tea 100 RANGE z a DEL soup GET tea Вывод: Course work for option 4.1, created by Ivan Ivanov. OK Error: RANGE Error: NOT_FOUND VALUE 100