| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 10 | 5 | 3 | 50.000% |
Исследуется новое цифровое устройство для хранения информации. Информация на устройстве хранится в виде последовательности ячеек, каждая из которых находится в одном из двух состояний, обозначаемых символами <<+>> и <<->>, и, таким образом, хранит один бит информации.
Назовём фрагментом группу соседних ячеек с одинаковым состоянием, слева от которой либо нет ячеек, либо находится ячейка в противоположном состоянии, и справа --- либо нет ячеек, либо находится ячейка в противоположном состоянии.
Операция записи позволяет выбрать любую пару соседних фрагментов разной длины и изменить состояние всех ячеек более короткого фрагмента на противоположное, объединяя таким образом два или три соседних фрагмента в один.
Требуется написать программу, которая по заданной исходной и итоговой последовательностям состояний ячеек определяет, можно ли из исходной последовательности получить итоговую с помощью последовательных операций записи.
Первая строка входных данных содержит целое число $q$ --- количество тестов.
Каждая из следующих $q$ строк содержит $s_i, t_i$ --- непустые последовательности символов <<+>> и <<->> одинаковой длины, разделённые одним пробелом. Эта строка означает, что в тесте номер $i$ из исходной последовательности состояний ячеек $s_i$ требуется получить итоговую последовательность~$t_i$.
Выходные данные должны содержать $q$ строк, где $i$-я строка равна <<Yes>>, если из исходной последовательности состояний ячеек $s_i$ можно получить итоговую последовательность $t_i,ドル или <<No>> в противном случае.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $\sum |s_i| \le 16,ドル $t_i$ состоит из символов << |
| 2 | 30 | $\sum |s_i| \le 1000,ドル $t_i$ состоит из символов << |
| 3 | 20 | $\sum |s_i| \le 10^6,ドル $t_i$ состоит из символов << |
| 4 | 20 | $\sum |s_i| \le 1000$ |
| 5 | 10 | $\sum |s_i| \le 10^6$ |
3 ++- +++ ++-- ++++ ++-+--+- ++++++++
Yes No Yes
3 ++-+-- ++---- ++-+-- +++--- -++- -++-
Yes No Yes