Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Рыцари, которые говорят только правду, и лжецы, которые всегда лгут, выстроились в ряд. (В ряду хотя бы один человек). Каждый из них произнёс фразу «Все мои соседи лжецы». Обозначим рыцаря буквой Р, а лжеца — буквой Л. Тогда каждой последовательности рыцарей и лжецов, для которой выполняется условие задачи, соответствует некоторое слово.
Опишите это слово, используя формулу, которая называется регулярным выражением. Такое выражение строится с помощью описываемых ниже операций "итерация", "умножение", "сложение".
Так для повторения блока из нескольких букв используйте операцию «звездочка» (итерация), например, (abb)* задает множество слов {пустое слово, abb, abbabb, abbabbabb, …}. Умножение множеств (эту операцию, как обычно в алгебре, изображают точкой приписыванием второго операнда вслед за первым, что мы и будем делать), описывает склейку всех слов первого множества со словами второго (третьего и т.д.), например a*cb* обозначает множество слов: {с, ac, cb, acb, aac,..., aaa...acb...b, ...}. Обратите внимание что слова, в которых нет букв a или b, получаются за счет того, что результат итерации может не содержать символов, то есть быть пустым словом.
Последней операцией, которая используется в формулах, является сложение. Сложение соответствует объединению множеств. Так, обозначение (a+b)*c+d(ac*+) описывает множество всех последовательностей из букв a и b (обозначается (a+b)*), к концу которых присоединена буква c, объединенного с множеством слов, начинающихся с буквы d, за которой следует буква a, а за ней любое число букв c и ещё одним однобуквенным словом (d умножить на пустое слово — это d)."
Слева приведены примеры слов, которые удовлетворяют нашему условию, справа примеры слов, которые не удовлетворяют ему. Благодаря подсветке вы можете видеть, какие из этих примеров и контрпримеров удовлетворяют построенному вами выражению, а какие — нет.
В качестве начального решения вы можете видеть выражение, которому удовлетворяет слово Р и пустое слово.
Первое слагаемое- все такие слова, которые начинаются на Р и заканчиваются на Р, так как сначала идет Р, затем снова Р идти не может, трех Л подряд также быть не может, значит далее Л или ЛЛ, а затем снова Р и т.д. Второе слагаемое- все такие слова, которые начинаются на Л и заканчиваются на Р, т.к. сначала идет Л, затем обязательно Р, затем Р идти не может и ЛЛЛ идти не может, значит Л или ЛЛ и т.д. В конце должно быть Р. Третье слагаемое- все такие слова, которые начинаются на Р и заканчиваются на Л, т.к. предпоследняя буква Л не может быть, значит мы просто убираем последнюю Л и получаем первый случай. Последнее слагаемое- все такие слова, которые начинаются на Л и заканчиваются на Л, т.к. вторая буква обязательно Р, далее снова Р не может идти, ЛЛЛ также не может идти, значит Л или ЛЛ, далее мы повторяем рассуждения, но в конце, чтобы не было две Л, мы добавляем РЛ,