1861B.md (2916B)
1 Source: https://codeforces.com/problemset/problem/1861/B 2 3 B. Two Binary Strings 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 You are given two strings $a$ and $b$ of equal length, consisting of only characters 0 and/or 1; both strings start with character 0 and end with character 1. 22 23 You can perform the following operation any number of times (possibly zero): 24 25 * choose one of the strings and two equal characters in it; then turn all characters between them into those characters. 26 27 Formally, you choose one of these two strings (let the chosen string be $s$), then pick two integers $l$ and $r$ such that $1 \le l \lt r \le |s|$ and $s_l = s_r$, then replace every character $s_i$ such that $l \lt i \lt r$ with $s_l$. 28 29 For example, if the chosen string is 010101, you can transform it into one of the following strings by applying one operation: 30 31 * 000101 if you choose $l = 1$ and $r = 3$; 32 * 000001 if you choose $l = 1$ and $r = 5$; 33 * 010001 if you choose $l = 3$ and $r = 5$; 34 * 010111 if you choose $l = 4$ and $r = 6$; 35 * 011111 if you choose $l = 2$ and $r = 6$; 36 * 011101 if you choose $l = 2$ and $r = 4$. 37 38 You have to determine if it's possible to make the given strings equal by applying this operation any number of times. 39 40 Input 41 42 The first line contains a single integer $t$ ($1 \le t \le 2000$) — the number of test cases. 43 44 Each test case consists of two lines: 45 46 * the first line contains the string $a$ ($2 \le |a| \le 5000$), consisting of only characters 0 and/or 1. 47 * the second line contains the string $b$ ($2 \le |b| \le 5000$), consisting of only characters 0 and/or 1. 48 49 Additional constraints on the input: 50 51 * in each test case, $|a| = |b|$ (the strings have equal length); 52 * in each test case, both strings start with 0 and end with 1; 53 * the total length of all strings $a$ in all test cases does not exceed $5000$. 54 55 Output 56 57 For each test case, print YES if it is possible to make the strings equal. Otherwise, print NO. You can print each letter in any register. 58 59 Example 60 61 Input 62 63 ``` 64 7 65 66 01010001 67 68 01110101 69 70 01001 71 72 01001 73 74 000101 75 76 010111 77 78 00001 79 80 01111 81 82 011 83 84 001 85 86 001001 87 88 011011 89 90 010001 91 92 011011 93 ``` 94 95 Output 96 97 ``` 98 YES 99 YES 100 YES 101 NO 102 NO 103 NO 104 YES 105 ``` 106 107 Note 108 109 In the first test case, we can perform the following operations: 110 111 1. choose the string $a$, $l = 2$, $r = 4$; after this operation, $a$ is 01110001, $b$ is 01110101; 112 2. choose the string $b$, $l = 5$, $r = 7$; after this operation, $a$ is 01110001, $b$ is 01110001. 113 114 In the second test case, the strings are already equal. 115 116 In the third test case, we can perform the following operations: 117 118 1. choose the string $a$, $l = 4$, $r = 6$; after this operation, $a$ is 000111, $b$ is 010111; 119 2. choose the string $b$, $l = 1$, $r = 3$; after this operation, $a$ is 000111, $b$ is 000111; 120 121 In the fourth and fifth test cases, it's impossible to make the given strings equal.