codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.