Содержание

Вариант 4.7. Прайс-лист запчастей

Все варианты на «Хорошо» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты

Уровень: Хорошо.

Постановка задачи

name — артикул запчасти, price — её цена в копейках. Артикулы, даже состоящие из цифр, сравниваются как строки по ASCII.

Разработайте каталог именованных позиций с ценами. Помимо точного поиска он должен поддерживать получение наименьшего имени, не меньшего заданного и упорядоченной выборки по диапазону имён.

Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.

Данные и начальное состояние

Операции

Команда Действие Ответ
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.7, 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.7, 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.7, 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.7, created by Ivan Ivanov.
OK
Error: RANGE
Error: NOT_FOUND
VALUE 100