====== Вариант 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