Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
916. Минимизация шаблона
Задачи на идеюОлимпиадные задачи на русском языке
| 11/12/2005 | Районно-городские командные соревнования (5) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для поиска слов, состоящих из латинских букв, в некотором словаре используется шаблон, в котором '?' означает ровно один произвольный символ, а '*' – ноль или более произвольных символов. Некоторые шаблоны являются эквивалентными, то есть соответствуют одинаковому множеству слов. Например, оба шаблона "*??*a" и "?*?a" соответствуют словам из трех или более букв, оканчивающимся на букву 'a', но второй шаблон короче.
Напишите программу, которая находит самый короткий шаблон, эквивалентный заданному.
Входной файл содержит несколько шаблонов длиной от 1 до 50 символов, состоящих из латинских букв и символов '?' и '*'. Каждый шаблон записан на отдельной строке.
В выходной файл для каждого шаблона вывести на соответствующей строке его минимальный эквивалент. Если существует несколько вариантов, вывести первый в лексикографическом порядке ('*' идет в алфавите раньше '?')
Пример ввода
*??*a T***nd?* *?*?*?*
Вывод для примера
*??a T*nd*? *???
