====== Вариант 3.5. Двунаправленный справочник адресов ======
[[:courses:algorithms_structures:cw_2026:grade3:start|Все варианты на «Удовлетворительно»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]]
Уровень: **Удовлетворительно**.
===== Постановка задачи =====
domain — условное имя узла сети без точек; ip — его адрес, записанный одним целым числом.
Разработайте двунаправленный справочник взаимно однозначных соответствий строковых имён и числовых адресов. Искать соответствие необходимо одинаково эффективно в обоих направлениях.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
===== Данные и начальное состояние =====
* ''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.5, 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.5, 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.5, 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.5, created by Ivan Ivanov.
OK
OK
Error: EXISTS
VALUE 1
VALUE alpha