2242D.md (2161B)
1 Source: https://codeforces.com/problemset/problem/2242/D 2 3 D. Two Digit Strings 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 512 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$, consisting only of digits. In one operation, you can choose two adjacent characters in either of these two strings and replace them with their sum modulo $10$. For example, from the string $57246$ you can obtain the following strings in one operation: 22 23 * $\mathbf{57}246 \rightarrow 2246$; 24 * $5\mathbf{72}46 \rightarrow 5946$; 25 * $57\mathbf{24}6 \rightarrow 5766$; 26 * $572\mathbf{46} \rightarrow 5720$; 27 28 Note that after such an operation, the length of the string always decreases by exactly $1$. 29 30 You can perform any number of such operations (even zero). You have to make these strings equal ($|a| = |b|$ and $a_i = b_i$ for all $i$ from $1$ to $|a|$). Calculate the maximum possible length of the resulting equal strings. 31 32 Input 33 34 The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^3$) — the number of test cases. 35 36 The first line of each test case contains a string $a$ ($1 \le |a| \le 5 \cdot 10^3$), consisting only of digits. 37 38 The second line of each test case contains a string $b$ ($1 \le |b| \le 5 \cdot 10^3$), consisting only of digits. 39 40 Additional constraint on the input: $\sum (|a| + |b|) $ across all test cases does not exceed $10^4$. 41 42 Output 43 44 For each test case, print one integer — the maximum possible length of the resulting equal strings. If you can't make the strings equal, print -1. 45 46 Example 47 48 Input 49 50 ``` 51 3 52 53 5147 54 55 44441 56 57 2194 58 59 5602 60 61 123450 62 63 012345 64 ``` 65 66 Output 67 68 ``` 69 2 70 71 -1 72 73 5 74 ``` 75 76 Note 77 78 In the first example from the statement, the maximum length you can obtain is 2: 79 80 * $\mathbf{51}47 \rightarrow 6\mathbf{47} \rightarrow 61$; 81 * $\mathbf{44}441 \rightarrow \mathbf{84}41 \rightarrow \mathbf{24}1 \rightarrow 61$. 82 83 In the second example from the statement, you can't make strings $a$ and $b$ equal, so the answer is -1. 84 85 In the third example from the statement, the maximum length you can obtain is 5: 86 87 * $1234\mathbf{50} \rightarrow 12345$; 88 * $\mathbf{01}2345 \rightarrow 12345$.