В ряд выстроены $$$n$$$ ламп с номерами от $$$1$$$ до $$$n$$$, изначально они выключены. Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):
Определите, можете ли вы достичь конфигурации $$$s$$$, где $$$s_i = 1$$$ означает, что $$$i$$$-я лампа включена, а в противном случае $$$s_i = 0$$$.
$$${}^\dagger$$$ Соседними считаются только лампы $$$i$$$ и $$$i + 1$$$ для всех $$$1 \le i < n$$$. Обратите внимание, что лампы $$$n$$$ и $$$1$$$ не являются соседними при $$$n \ne 2$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 50$$$) — количество ламп.
Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$ — желаемую конечную конфигурацию.
Для каждого набора входных данных выведите в отдельной строке «YES», если возможно достичь конфигурацию $$$s$$$ путем применения данной операции любое количество раз. В противном случае выведите «NO».
510110101011010100100111060000001112111111111111
YES NO YES NO YES
В первом наборе входных данных последовательность операций могла бы быть следующей (обратите внимание, что изначально все элементы $$$s$$$ равны нулю): $$$\mathtt{0000000000} \to \mathtt{\color{red}{1}0000000\color{red}{1}0} \to \mathtt{1\color{red}{1}00000\color{red}{1}10} \to \mathtt{110\color{red}{1}0\color{red}{1}0110}$$$.
В третьем наборе входных данных не нужно выполнять никаких операций.
В четвертом наборе входных данных невозможно выполнить никакую операцию, но нам нужно, чтобы горела первая лампа. Поэтому достичь желаемой конфигурации невозможно.
| Codeforces Global Round 25 |
|---|
| Закончено |
