Все варианты на «Удовлетворительно» · Общие требования и формат ввода/вывода · Регламент выполнения и защиты
Уровень: Удовлетворительно.
Строковое поле domain — артикул товара, числовое поле ip — номер складской ячейки. Команда IP ищет ячейку по артикулу, DOMAIN — артикул по ячейке. Один артикул занимает ровно одну ячейку; количество товара не моделируется.
Разработайте двунаправленный справочник взаимно однозначных соответствий строковых имён и числовых адресов. Искать соответствие необходимо одинаково эффективно в обоих направлениях.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
domain — непустой строковый идентификатор по общему формату; реальное доменное имя с точками разбирать не требуется.ip — целое число от 0 до 4294967295. Точечная запись IPv4 не используется.| Команда | Действие | Ответ |
|---|---|---|
ADD domain ip | Создать новую пару; оба значения должны быть свободны. | OK; если хотя бы одно значение занято, Error: EXISTS |
SET domain ip | Заменить числовой адрес существующего имени. | OK; имя отсутствует — Error: NOT_FOUND; адрес занят другим именем — Error: EXISTS |
IP domain | Найти числовое значение по строковому. | VALUE ip; при отсутствии NONE |
DOMAIN ip | Найти строковое значение по числовому. | VALUE domain; при отсутствии NONE |
DEL domain | Удалить соответствие целиком. | OK; при отсутствии имени Error: NOT_FOUND |
LIST | Получить пары по возрастанию строкового имени. | ITEMS n, затем n строк domain ip |
SET с прежним собственным адресом разрешён и возвращает OK. После изменения прежний адрес освобождается. Неудачный ADD/SET не меняет ни одно направление поиска. После DEL оба поиска перестают находить пару.
Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.
Операции по ключу — ожидаемо амортизированно O(L) с допустимым худшим случаем O(nL), либо гарантированно O(L·log(n+2)), где L — длина строкового ключа. LIST — не хуже O(n·log(n+2)·L). Память — O(nL); поиск в одном из направлений не должен требовать обычного полного перебора всех пар.
В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.
Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:
Course work for option 3.15, created by Ivan Ivanov.
Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.
Ввод:
1 5 ADD alpha 1 ADD beta 2 IP alpha DOMAIN 2 LIST
Вывод:
Course work for option 3.15, created by Ivan Ivanov. OK OK VALUE 1 VALUE beta ITEMS 2 alpha 1 beta 2
Ввод:
1 6 ADD alpha 1 SET alpha 3 DOMAIN 1 DOMAIN 3 DEL alpha IP alpha
Вывод:
Course work for option 3.15, created by Ivan Ivanov. OK OK NONE VALUE alpha OK NONE
Ввод:
1 5 ADD alpha 1 ADD beta 2 SET alpha 2 IP alpha DOMAIN 1
Вывод:
Course work for option 3.15, created by Ivan Ivanov. OK OK Error: EXISTS VALUE 1 VALUE alpha