codeforces-scrape

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

1834B.md (2824B)


      1 Source: https://codeforces.com/problemset/problem/1834/B
      2 
      3 B. Maximum Strength
      4 
      5 time limit per test
      6 
      7 1 second
      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 Fedya is playing a new game called "The Legend of Link", in which one of the character's abilities is to combine two materials into one weapon. Each material has its own strength, which can be represented by a positive integer $x$. The strength of the resulting weapon is determined as the sum of the absolute differences of the digits in the decimal representation of the integers at each position.
     22 
     23 Formally, let the first material have strength $X = \overline{x_{1}x_{2} \ldots x_{n}}$, and the second material have strength $Y = \overline{y_{1}y_{2} \ldots y_{n}}$. Then the strength of the weapon is calculated as $|x_{1} - y_{1}| + |x_{2} - y_{2}| + \ldots + |x_{n} - y_{n}|$. If the integers have different lengths, then the shorter integer is padded with leading zeros.
     24 
     25 Fedya has an unlimited supply of materials with all possible strengths from $L$ to $R$, inclusive. Help him find the maximum possible strength of the weapon he can obtain.
     26 
     27 An integer $C = \overline{c_{1}c_{2} \ldots c_{k}}$ is defined as an integer obtained by sequentially writing the digits $c_1, c_2, \ldots, c_k$ from left to right, i.e. $10^{k-1} \cdot c_1 + 10^{k-2} \cdot c_2 + \ldots + c_k$.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.
     32 
     33 The first line of each test case contains two integers $L$ and $R$ ($1 \le L \le R \lt 10^{100}$) — the decimal representation of the integers representing the minimum and maximum strength of the materials that Fedya has. It is guaranteed that the integers $L$ and $R$ do not contain leading zeros.
     34 
     35 Note that the input data may not fit into standard $32$-bit or $64$-bit integer data types.
     36 
     37 Output
     38 
     39 For each test case print one integer — the maximum possible strength of the weapon that Fedya can obtain from the given materials.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 6
     47 
     48 53 57
     49 
     50 179 239
     51 
     52 13 37
     53 
     54 132228 132228
     55 
     56 54943329752812629795 55157581939688863366
     57 
     58 88 1914
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 4
     65 19
     66 11
     67 0
     68 163
     69 28
     70 ```
     71 
     72 Note
     73 
     74 In the first test case, the weapon made from materials with strengths $53$ and $57$ will have the maximum possible strength: $|5 - 5| + |3 - 7| = 4$.
     75 
     76 In the second test case, the maximum strength is achieved with materials with strengths $190$ and $209$: $|1 - 2| + |9 - 0| + |0 - 9| = 19$.
     77 
     78 In the fourth test case, there is only one valid strength, so the answer is $0$.
     79 
     80 In the sixth test case, the maximum strength is achieved with materials with strengths $1909$ and $90$: $|1 - 0| + |9 - 0| + |0 - 9| + |9 - 0| = 28$. Note that the shorter integer was padded with leading zeros.