Инструменты пользователя

Инструменты сайта


courses:algorithms_structures:cw_2026:grade3:15

Вариант 3.15. Распределение складских ячеек

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

Строковое поле 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. Поиск в обе стороны

Ввод:

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

Пример 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

Пример 3. Конфликт не меняет пару

Ввод:

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
courses/algorithms_structures/cw_2026/grade3/15.txt · Последнее изменение: — 127.0.0.1