codeforces-scrape

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

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$.