ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1414. Астрономическая база данных

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
После вывода на орбиту Земли телескопа Hubble количество известных человечеству звёзд заметно возросло. Можно представить себе, насколько увеличится их количество, когда человек освоит гиперпространственный прыжок!
Предусмотрительные астрономы уже сейчас хотят подготовиться к этому моменту. Они создают программное обеспечение для ведения базы данных всех известных звёзд. База данных будет многопользовательской, и все астрономы вселенной смогут принять участия в её заполнении. Чтобы сделать программное обеспечение максимально удобным для пользователя, необходимо реализовать функцию контекстной подсказки: при вводе очередного символа названия звезды, ПО должно предлагать список звёзд, названия которых начинаются с уже введённых пользователем символов. Вам придётся помочь астрономам в их космической проблеме, и разработать прототип алгоритма, который позже будет использован для ведения астрономической базы данных.

Исходные данные

На вход вашей программе подаётся последовательность операций, по одной в строке. Первый символ строки обозначает тип операции. Оставшиеся символы строки (малые латинские буквы или цифры) — это аргумент операции.
Типы операций:
'+' — добавить название звезды в базу данных. Аргумент этой операции — это название звезды, которое необходимо добавить. Поскольку работа с базой данных идёт в многопользовательском режиме, информация об одной звезде может быть введена в базу несколько раз. В начале выполнения программы считайте, что в базе данных содержится единственное слово «sun».
'?' — найти все названия, начинающиеся с символов указанных в аргументе этой команды.
Можете считать, что во входных данных содержится не более 10000 операций, а все аргументы операций содержат не менее одного и не более 20 символов.

Результат

На операцию '+' выводить ничего не надо.
На каждую операцию '?' необходимо вывести результат запроса: аргумент команды, а вслед за ним список названий звёзд, начинающихся с данных символов и содержащихся на момент запроса в базе данных.
Названия звёзд необходимо выводить в лексикографическом порядке, по одному в строке, без повторений.
Если таких названий больше 20, то необходимо вывести лишь первые 20. Названия должны быть напечатаны с отступом слева в два пробела, как это показано в примере выходных данных (в примере для наглядности пробелы заменены точками).

Пример

исходные данныерезультат
?e
+earth
+egg
?e
+eagle
+earth
?ea
e
e
..earth
..egg
ea
..eagle
..earth
Автор задачи: Павел Егоров
Источник задачи: Чемпионат Уральского государственного университета, 29 октября 2005