Содержание
Вариант 4.6. Каталог тарифов
Все варианты на «Хорошо» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Хорошо.
Постановка задачи
name — название тарифа, price — стоимость в копейках. LOWER выбирает следующий тариф по названию, а не по цене.
Разработайте каталог именованных позиций с ценами. Помимо точного поиска он должен поддерживать получение наименьшего имени, не меньшего заданного и упорядоченной выборки по диапазону имён.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
Данные и начальное состояние
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.6, 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.6, 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.6, 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.6, created by Ivan Ivanov. OK Error: RANGE Error: NOT_FOUND VALUE 100
