Codeforces Round 979 (Div. 2) |
---|
Finished |
Alice and Bob are playing a game. There is a list of $$$n$$$ booleans, each of which is either true or false, given as a binary string $$$^{\text{∗}}$$$ of length $$$n$$$ (where $$$\texttt{1}$$$ represents true, and $$$\texttt{0}$$$ represents false). Initially, there are no operators between the booleans.
Alice and Bob will take alternate turns placing and or or between the booleans, with Alice going first. Thus, the game will consist of $$$n-1$$$ turns since there are $$$n$$$ booleans. Alice aims for the final statement to evaluate to true, while Bob aims for it to evaluate to false. Given the list of boolean values, determine whether Alice will win if both players play optimally.
To evaluate the final expression, repeatedly perform the following steps until the statement consists of a single true or false:
$$$^{\text{∗}}$$$A binary string is a string that only consists of characters $$$\texttt{0}$$$ and $$$\texttt{1}$$$
The first line contains $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the length of the string.
The second line contains a binary string of length $$$n$$$, consisting of characters $$$\texttt{0}$$$ and $$$\texttt{1}$$$ — the list of boolean values.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each testcase, output "YES" (without quotes) if Alice wins, and "NO" (without quotes) otherwise.
You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).
5211301012101111111100100111111011801000010
YES NO YES YES NO
In the first testcase, Alice can place and between the two booleans. The game ends as there are no other places to place operators, and Alice wins because true and true is true.
In the second testcase, Alice can place or between the middle true and the left false. Bob can place and between the middle true and the right false. The statement false or true and false is false.
Note that these examples may not be the best strategies for either Alice or Bob.
Name |
---|