Задача: Великая стройка
Сережа и Саша решили все задачи, поэтому решили немного отвлечься от лекции. Сережа начал строить строки по определенному правилу:
• На нулевом шаге строка состоит из одной английской буквы b
• На шаге 3k + 1, k 2 0 он прибавляет слева от строки букву а, а справа букву с
• На шаге 3k + 2, k 2 0 он прибавляет наоборот слева от строки букву с, а справа букву а
• И на шаге 3k + 3, k 2 0 Сережа прибавляет справа и слева от строки букву ь
Но иногда Сережа решает подшутить над Сашей — он может дать ему произвольную строку и сказать, что построил ее по правилу выше, хотя на самом деле это может быть не так. Саша хочет научиться проверять, обманывает его Сережа или нет.
Помогите Саше — по данной строке определите, могла ли она получиться в ходе построения, описанного выше, и если могла — то на каком шаге?
1 Ответ
Решение:
Для решения задачи нужно проанализировать структуру строки, которую дал Сережа, и проверить, соответствует ли она правилам построения.
Проверка на наличие символов: Строка должна содержать только символы ‘a’, ‘b’, и ‘c’. Если есть другие символы, строка не могла быть построена по правилам.
Поиск центрального ‘b’: Необходимо найти центральный символ ‘b’. Если ‘b’ нет или их несколько, строка не соответствует правилам.
Анализ структуры вокруг ‘b’: Вокруг центрального ‘b’ должны быть символы ‘a’ и ‘c’, добавляемые по определенным правилам. Проверяем, соответствует ли структура строки одному из шагов построения (3k+1, 3k+2, 3k+3).
Определение шага: Если строка соответствует правилам, нужно определить шаг построения. Это можно сделать, посчитав количество добавленных символов ‘a’, ‘c’ и ‘b’ с каждой стороны от центрального ‘b’.
Проверка на соответствие шагу: Убеждаемся, что найденный шаг соответствует структуре строки.
Пример:
Строка: «acbbca»
Символы: Только ‘a’, ‘b’, ‘c’ — подходит.
Центральный ‘b’: Один ‘b’ в центре — подходит.
Структура: Вокруг ‘b’ есть ‘a’ и ‘c’.
Шаг: Это шаг 3k+3, где k=0, так как слева и справа от «b» добавили по одному символу («ac»). Изначальная строка «b» -> «cbс» (шаг 3) -> «acbbca» (шаг 6) и т.д.
Важно учитывать, что строка может быть построена только на одном определенном шаге.
