====== Вариант 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