ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 102786
Тема:    [ Динамическое программирование (прочее) ]
Сложность: 4
Классы:
Название задачи: Ну и имечко! .
В корзину
Прислать комментарий

Условие

В семье программистов родился ребенок. Папа-программист хочет назвать ребенка так, чтобы его имя подходило под шаблон P, а мама-программист настаивает на шаблоне M. Найдите самое короткое имя, удовлетворяющее обоим шаблонам, или сообщите, что такого имени не существует и семья находится на грани развода.

Шаблон представляет собой последовательность букв русского алфавита (буква «ё» не используется) и специальных символов, которые имеют следующие значения: 
? любая буква 
* любое (возможно нулевое) число букв 
[P]  любая буква из диапазона P
[!P] любая буква не из диапазона P
{n} предыдущий символ, повторенный ровно n раз
{n;}  предыдущий символ, повторенный не менее n раз 
{n;m} предыдущий символ, повторенный от n до m раз 
предыдущий символ, повторенный не менее одного раза

При этом 0 ≤ n ≤ m ≤ 10. Диапазон задается перечислением через запятуюсимволов и интервалов символов. Интервал символов записывается в виде a-b, что означает любую букву, расположенную в алфавите между a и b включительно.
Символы могут комбинироваться. Например, запись [а,о,е,у,и,ы,э-я]@ означает произвольную непустую последовательность гласных (необязательно повторяющихся). Запрещается записывать подряд фигурные
скобки и символы @.

Входные данные

В первой строке входного файла записан шаблон папы, а во второй – шаблон мамы. Длина каждого шаблона не превосходит 80 символов.

Выходные данные

Выведите в выходной файла кратчайшее имя ребенка, удовлетворяющее обоим шаблонам, если такое имя существует. Имя ребенка должно состоять из букв русского алфавита. Большие и маленькие буквы не различаются. В случае нескольких возможных имен требуется вывести первое по алфавиту. Если искомого имени не существует, выведите сообщение «NO SOLUTION».

Пример входного файла

?ик*т[а-о][л-р]*
В??тор*

Пример выходного файла

Виктор

Решение

Скачать архив тестов и решений

Эта задача решается аналогично предыдущей, но требует гораздо более тщательного программирования.

Источники и прецеденты использования

книга
предмет информатика
Автор Беров В., Лапунов А., Матюхин В., Пономарев А.
Название Особенности национальных задач по информатике
Издательство Триада-С
Год издания 2000
глава
Номер 1
Название Динамическое программирование
Задача
Номер 9

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .