====== Вариант 4.9. Каталог географических названий ======
[[:courses:algorithms_structures:cw_2026:grade4:start|Все варианты на «Хорошо»]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и формат ввода/вывода]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]]
Уровень: **Хорошо**.
===== Постановка задачи =====
word — предварительно нормализованное географическое название из строчных латинских букв, frequency — заданная числовая характеристика. Преобразование Unicode и пробелов не требуется.
Разработайте каталог строковых имён с числовыми характеристиками. Необходимо быстро искать все имена с заданным началом, ограничивать число результатов и считать общее количество совпадений.
Выберите и обоснуйте структуры хранения и алгоритмы выполнения операций самостоятельно. Указанные далее поведение и оценки эффективности обязательны; способ реализации не предписывается. Имена команд и полей в таблице фиксированы: предметная трактовка не меняет машинный формат.
===== Данные и начальное состояние =====
* ''word'' — строка из 1–32 строчных латинских букв a–z.
* ''prefix'' — строка из 1–32 строчных латинских букв либо символ ''*'', обозначающий пустое начало и совпадение со всеми именами.
* ''frequency'' — целое число от 0 до 1000000000, ''k'' — от 0 до 100000. Начальное состояние пустое.
===== Операции =====
^ Команда ^ Действие ^ Ответ ^
| ''PUT word frequency'' | Создать имя либо заменить его характеристику. | OK |
| ''GET word'' | Найти точное имя. | VALUE frequency; при отсутствии NONE |
| ''DEL word'' | Удалить точное имя. | OK; при отсутствии Error: NOT_FOUND |
| ''PREFIX prefix k'' | Выдать первые min(k,m) совпадений лексикографически, где m — число совпавших имён. | ITEMS r, затем r строк word frequency |
| ''COUNT prefix'' | Посчитать все различные имена с указанным началом. | VALUE m |
===== Правила выполнения и ошибки =====
Нулевая характеристика не удаляет имя. Одно имя может быть началом другого, но это две разные записи. COUNT считает имена, а не сумму frequency. GET/PREFIX не изменяют frequency. При k=0 выдаётся ITEMS 0.
Коды ошибок в тексте обозначают точный ответ Error: CODE по общей спецификации. На каждую успешную команду, включая операцию без фактического изменения данных, выводится ответ из таблицы.
===== Требования к эффективности =====
PUT, GET, DEL, COUNT — O(L) в худшем случае, где L — длина аргумента. PREFIX — O(L + rW), где W=32 — максимальная длина имени и r — число выданных записей; просмотр всех совпадений при малом k не допускается. Память — O(суммы длин сохранённых имён + 1). Способ организации данных студент выбирает самостоятельно.
В отчёте обоснуйте эти оценки и подтвердите их экспериментами; учтите худшие случаи и стоимость вывода результатов. Полное условие по разрешённым средствам, режимам 1/6 и обработке ошибок приведено в общих требованиях.
===== Формат ввода и вывода =====
Первая строка stdin — 1, вторая — число q, затем q строк команд из таблицы. Для справки подайте только строку 6. Общая лексика, разделители и порядок проверки ошибок обязательны. Первая строка stdout для этого варианта:
Course work for option 4.9, created by Ivan Ivanov.
Вместо Ivan Ivanov укажите собственные имя и фамилию. Далее идут ответы на команды; для ITEMS k — ещё k строк записей. Все приведённые примеры являются отдельными запусками с начальным состоянием.
===== Примеры =====
==== Пример 1. Подсчёт и порядок ====
Ввод:
1
5
PUT cat 2
PUT car 0
PUT dog 1
COUNT ca
PREFIX ca 5
Вывод:
Course work for option 4.9, created by Ivan Ivanov.
OK
OK
OK
VALUE 2
ITEMS 2
car 0
cat 2
==== Пример 2. Имя является началом другого ====
Ввод:
1
6
PUT a 1
PUT ab 2
DEL a
COUNT *
PREFIX * 0
GET ab
Вывод:
Course work for option 4.9, created by Ivan Ivanov.
OK
OK
OK
VALUE 1
ITEMS 0
VALUE 2
==== Пример 3. Неверное имя ====
Ввод:
1
4
PUT cat 2
PUT Cat 3
DEL car
GET cat
Вывод:
Course work for option 4.9, created by Ivan Ivanov.
OK
Error: INPUT
Error: NOT_FOUND
VALUE 2