Задача №113548. Накопитель
Исследуется новое цифровое устройство для хранения информации. Информация на устройстве хранится в виде последовательности ячеек, каждая из которых находится в одном из двух состояний, обозначаемых символами «+» и «-», и, таким образом, хранит один бит информации.
Назовём фрагментом группу соседних ячеек с одинаковым состоянием, слева от которой либо нет ячеек, либо находится ячейка в противоположном состоянии, и справа — либо нет ячеек, либо находится ячейка в противоположном состоянии.
Операция записи позволяет выбрать любую пару соседних фрагментов разной длины и изменить состояние всех ячеек более короткого фрагмента на противоположное, объединяя таким образом два или три соседних фрагмента в один.
Требуется написать программу, которая по заданной исходной и итоговой последовательностям состояний ячеек определяет, можно ли из исходной последовательности получить итоговую с помощью последовательных операций записи.
Первая строка входных данных содержит целое положительное число q — количество тестов.
Каждая из следующих q строк содержит si, ti — непустые последовательности символов «+» и «-» одинаковой длины, разделённые одним пробелом. Эта строка означает, что в тесте номер i из исходной последовательности состояний ячеек si требуется получить итоговую последовательность ti.
Выходные данные должны содержать q строк, где i-я строка равна «Yes», если из исходной последовательности состояний ячеек si можно получить итоговую последовательность ti, или «No» в противном случае.
3 ++- +++ ++-- ++++ ++-+--+- ++++++++
Yes No Yes
3 ++-+-- ++---- ++-+-- +++--- -++- -++-
Yes No Yes