В семье программистов родился ребенок. Папа-программист хочет назвать ребенка так, чтобы его имя подходило под шаблон 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».

Пример входного файла
?ик*т[а-о][л-р]*
В??тор*

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

   Решение

Страница: << 2 3 4 5 6 7 8 [Всего задач: 38]      

Двое играют в такую игру. Один задумывает натуральное число n, а другой задаёт вопросы типа «верно ли, что n не меньше x» (число x он может выбирать по своему усмотрению) и получает ответы «да» или «нет». Каждой возможной стратегии T второго игрока сопоставим функцию f_T(n), равную числу вопросов (до отгадывания), если было задумано число n. Пусть, например, стратегия T состоит в том, что сначала задают вопросы: «верно ли, что n не меньше 10?», «верно ли, что n не меньше 20?», ... до тех пор, пока на какой-то вопрос «верно ли, что n не меньше 10(k + 1)» не будет дан ответ «нет», а затем задают вопросы «верно ли, что n не меньше 10k + 1», «верно ли, что n не меньше 10k + 2» и так далее. Тогда f_T(n) = a + 2 + ^{(n – a)}/₁₀, где a — последняя цифра числа n, то есть f_T(n) растёт примерно как ⁿ/₁₀.

а) Предложите стратегию, для которой функция f_T растёт медленнее.

б) Сравнивая две стратегии, удобно для произвольной стратегии Т вместо функции f_T ввести функцию f_T, значение которой для любого натурального числа n равно наибольшему из чисел f_T(k), где k пробегает значения от 1 до n. Оцените снизу f_T для произвольной стратегии T.

Прислать комментарий

Решение

На плоскости отмечены две точки на расстоянии 1. Разрешается, измерив циркулем расстояние между двумя отмеченными точками, провести окружность с центром в любой отмеченной точке с измеренным радиусом. Линейкой разрешается провести прямую через любые две отмеченные точки. При этом отмечаются новые точки – точки пересечения построенных линий. Пусть Ц(n) – наименьшее число линий, проведение которых одним циркулем позволяет получить две отмеченные точки на расстоянии n (n – натуральное). ЛЦ(n) – то же, но циркулем и линейкой. Докажите, что последовательность    неограничена.

Прислать комментарий

Решение

Дан квадрат со стороной 1. От него отсекают четыре уголка — четыре треугольника, у каждого из которых две стороны идут по сторонам квадрата и составляют 1/3 их длины. С полученным 8-угольником делают то же самое: от каждой вершины отрезают треугольник, две стороны которого составляют по 1/3 соответствующих сторон 8-угольника, и так далее. Получается последовательность многоугольников (каждый содержится в предыдущем). Найдите площадь фигуры, являющейся пересечением всех этих многоугольников (то есть образованной точками, принадлежащими всем многоугольникам).

Прислать комментарий

Решение

Страница: << 2 3 4 5 6 7 8 [Всего задач: 38]