1728C.md (1968B)
1 Source: https://codeforces.com/problemset/problem/1728/C 2 3 C. Digital Logarithm 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 Let's define $f(x)$ for a positive integer $x$ as the length of the base-10 representation of $x$ without leading zeros. I like to call it a digital logarithm. Similar to a digital root, if you are familiar with that. 22 23 You are given two arrays $a$ and $b$, each containing $n$ positive integers. In one operation, you do the following: 24 25 1. pick some integer $i$ from $1$ to $n$; 26 2. assign either $f(a_i)$ to $a_i$ or $f(b_i)$ to $b_i$. 27 28 Two arrays are considered similar to each other if you can rearrange the elements in both of them, so that they are equal (e. g. $a_i = b_i$ for all $i$ from $1$ to $n$). 29 30 What's the smallest number of operations required to make $a$ and $b$ similar to each other? 31 32 Input 33 34 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases. 35 36 The first line of the testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in each of the arrays. 37 38 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \lt 10^9$). 39 40 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_j \lt 10^9$). 41 42 The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each testcase, print the smallest number of operations required to make $a$ and $b$ similar to each other. 47 48 Example 49 50 Input 51 52 ``` 53 4 54 55 1 56 57 1 58 59 1000 60 61 4 62 63 1 2 3 4 64 65 3 1 4 2 66 67 3 68 69 2 9 3 70 71 1 100 9 72 73 10 74 75 75019 709259 5 611271314 9024533 81871864 9 3 6 4865 76 77 9503 2 371245467 6 7 37376159 8 364036498 52295554 169 78 ``` 79 80 Output 81 82 ``` 83 2 84 0 85 2 86 18 87 ``` 88 89 Note 90 91 In the first testcase, you can apply the digital logarithm to $b_1$ twice. 92 93 In the second testcase, the arrays are already similar to each other. 94 95 In the third testcase, you can first apply the digital logarithm to $a_1$, then to $b_2$.