Codeforces Round 958 (Div. 2) |
---|
Закончено |
Вам дана последовательность $$$[a_1,\ldots,a_n]$$$, где каждый элемент $$$a_i$$$ равен либо $$$0$$$, либо $$$1$$$. Вы можете применить несколько (возможно, нулевое количество) операций к последовательности. В каждой операции вы выбираете два целых числа $$$1\le l\le r\le |a|$$$ (где $$$|a|$$$ — текущая длина $$$a$$$) и заменяете $$$[a_l,\ldots,a_r]$$$ одним элементом $$$x$$$, где $$$x$$$ — большинство $$$[a_l,\ldots,a_r]$$$.
Здесь большинство последовательности, состоящей из $$$0$$$ и $$$1$$$, определяется следующим образом: предположим, что в последовательности содержится $$$c_0$$$ нулей и $$$c_1$$$ единиц соответственно.
Например, предположим, что $$$a=[1,0,0,0,1,1]$$$. Если мы выберем $$$l=1,r=2$$$, то результирующая последовательность будет $$$[0,0,0,1,1]$$$. Если мы выберем $$$l=4,r=6$$$, то результирующая последовательность будет $$$[1,0,0,1]$$$.
Определите, можно ли сделать $$$a=[1]$$$ с помощью конечного количества операций.
Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 4\cdot 10^4$$$). Далее следует описание наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$).
Вторая строка каждого набора содержит строку, состоящую из $$$0$$$ и $$$1$$$, описывающую последовательность $$$a$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам не превышает $$$2\cdot 10^5$$$.
Для каждого набора входных данных, если возможно сделать $$$a=[1]$$$, выведите YES. В противном случае выведите NO. Вы можете вывести ответ в любом регистре (верхний или нижний). Например, строки yEs, yes, Yes и YES будут распознаны как положительные ответы.
5101120191000000019000011000
No Yes No Yes No
В четвертом наборе входных данных изначально $$$a=[1,0,0,0,0,0,0,0,1]$$$. Допустимая последовательность операций:
Название |
---|