2030C.md (2847B)
1 Source: https://codeforces.com/problemset/problem/2030/C 2 3 C. A TRUE Battle 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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. 24 25 To evaluate the final expression, repeatedly perform the following steps until the statement consists of a single true or false: 26 27 * If the statement contains an and operator, choose any one and replace the subexpression surrounding it with its evaluation. 28 * Otherwise, the statement contains an or operator. Choose any one and replace the subexpression surrounding the or with its evaluation. 29 30 For example, the expression true or false and false is evaluated as true or (false and false) $=$ true or false $=$ true. It can be shown that the result of any compound statement is unique. 31 32 $^{\text{∗}}$A binary string is a string that only consists of characters $\texttt{0}$ and $\texttt{1}$ 33 34 Input 35 36 The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 37 38 The first line of each test case contains an integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the length of the string. 39 40 The second line contains a binary string of length $n$, consisting of characters $\texttt{0}$ and $\texttt{1}$ — the list of boolean values. 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each testcase, output "YES" (without quotes) if Alice wins, and "NO" (without quotes) otherwise. 47 48 You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response). 49 50 Example 51 52 Input 53 54 ``` 55 5 56 57 2 58 59 11 60 61 3 62 63 010 64 65 12 66 67 101111111100 68 69 10 70 71 0111111011 72 73 8 74 75 01000010 76 ``` 77 78 Output 79 80 ``` 81 YES 82 NO 83 YES 84 YES 85 NO 86 ``` 87 88 Note 89 90 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. 91 92 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. 93 94 Note that these examples may not be the best strategies for either Alice or Bob.