codeforces-scrape

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

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