1669D.md (3542B)
1 Source: https://codeforces.com/problemset/problem/1669/D 2 3 D. Colorful Stamp 4 5 time limit per test 6 7 1 second 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 A row of $n$ cells is given, all initially white. Using a stamp, you can stamp any two neighboring cells such that one becomes red and the other becomes blue. A stamp can be rotated, i.e. it can be used in both ways: as $\color{blue}{\texttt{B}}\color{red}{\texttt{R}}$ and as $\color{red}{\texttt{R}}\color{blue}{\texttt{B}}$. 22 23 During use, the stamp must completely fit on the given $n$ cells (it cannot be partially outside the cells). The stamp can be applied multiple times to the same cell. Each usage of the stamp recolors both cells that are under the stamp. 24 25 For example, one possible sequence of stamps to make the picture $\color{blue}{\texttt{B}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\color{blue}{\texttt{B}}\texttt{W}$ could be $\texttt{WWWWW} \to \texttt{WW}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\texttt{W} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\texttt{W} \to \color{blue}{\texttt{B}}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}\texttt{W}$. Here $\texttt{W}$, $\color{red}{\texttt{R}}$, and $\color{blue}{\texttt{B}}$ represent a white, red, or blue cell, respectively, and the cells that the stamp is used on are marked with an underline. 26 27 Given a final picture, is it possible to make it using the stamp zero or more times? 28 29 Input 30 31 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 32 33 The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^5$) — the length of the picture. 34 35 The second line of each test case contains a string $s$ — the picture you need to make. It is guaranteed that the length of $s$ is $n$ and that $s$ only consists of the characters $\texttt{W}$, $\texttt{R}$, and $\texttt{B}$, representing a white, red, or blue cell, respectively. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 38 39 Output 40 41 Output $t$ lines, each of which contains the answer to the corresponding test case. As an answer, output "YES" if it possible to make the picture using the stamp zero or more times, and "NO" otherwise. 42 43 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer). 44 45 Example 46 47 Input 48 49 ``` 50 12 51 52 5 53 54 BRBBW 55 56 1 57 58 B 59 60 2 61 62 WB 63 64 2 65 66 RW 67 68 3 69 70 BRB 71 72 3 73 74 RBB 75 76 7 77 78 WWWWWWW 79 80 9 81 82 RBWBWRRBW 83 84 10 85 86 BRBRBRBRRB 87 88 12 89 90 BBBRWWRRRWBR 91 92 10 93 94 BRBRBRBRBW 95 96 5 97 98 RBWBW 99 ``` 100 101 Output 102 103 ``` 104 YES 105 NO 106 NO 107 NO 108 YES 109 YES 110 YES 111 NO 112 YES 113 NO 114 YES 115 NO 116 ``` 117 118 Note 119 120 The first test case is explained in the statement. 121 122 For the second, third, and fourth test cases, it is not possible to stamp a single cell, so the answer is "NO". 123 124 For the fifth test case, you can use the stamp as follows: $\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{blue}{\texttt{B}}$. 125 126 For the sixth test case, you can use the stamp as follows: $\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}$. 127 128 For the seventh test case, you don't need to use the stamp at all.