2121E.md (2181B)
1 Source: https://codeforces.com/problemset/problem/2121/E 2 3 E. Sponsor of Your Problems 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 For two integers $a$ and $b$, we define $f(a, b)$ as the number of positions in the decimal representation of the numbers $a$ and $b$ where their digits are the same. For example, $f(12, 21) = 0$, $f(31, 37) = 1$, $f(19891, 18981) = 2$, $f(54321, 24361) = 3$. 22 23 You are given two integers $l$ and $r$ of the same length in decimal representation. Consider all integers $l \leq x \leq r$. Your task is to find the minimum value of $f(l, x) + f(x, r)$. 24 25 Input 26 27 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows. 28 29 Each test case consists of a single line containing two integers $l$ and $r$ ($1 \leq l \leq r \lt 10^9$). 30 31 It is guaranteed that the numbers $l$ and $r$ have the same length in decimal representation and do not have leading zeros. 32 33 Output 34 35 For each test case, output the minimum value of $f(l, x) + f(x, r)$ among all integer values $l \leq x \leq r$. 36 37 Example 38 39 Input 40 41 ``` 42 14 43 44 1 1 45 46 2 3 47 48 4 6 49 50 15 16 51 52 17 19 53 54 199 201 55 56 899 999 57 58 1990 2001 59 60 6309 6409 61 62 12345 12501 63 64 19987 20093 65 66 746814 747932 67 68 900990999 900991010 69 70 999999999 999999999 71 ``` 72 73 Output 74 75 ``` 76 2 77 1 78 0 79 3 80 2 81 2 82 1 83 3 84 3 85 4 86 3 87 5 88 12 89 18 90 ``` 91 92 Note 93 94 In the first test case, you can choose $x = 1$. Then $f(1, 1) + f(1, 1) = 1 + 1 = 2$. 95 96 In the second test case, you can choose $x = 2$. Then $f(2, 2) + f(2, 3) = 1 + 0 = 1$. 97 98 In the third test case, you can choose $x = 5$. Then $f(4, 5) + f(5, 6) = 0 + 0 = 0$. 99 100 In the fourth test case, you can choose $x = 15$. Then $f(15, 15) + f(15, 16) = 2 + 1 = 3$. 101 102 In the fifth test case, you can choose $x = 18$. Then $f(17, 18) + f(18, 19) = 1 + 1 = 2$. 103 104 In the sixth test case, you can choose $x = 200$. Then $f(199, 200) + f(200, 201) = 0 + 2 = 2$. 105 106 In the seventh test case, you can choose $x = 900$. Then $f(899, 900) + f(900, 999) = 0 + 1 = 1$. 107 108 In the eighth test case, you can choose $x = 1992$. Then $f(1990, 1992) + f(1992, 2001) = 3 + 0 = 3$.