CF1834B.Maximum Strength
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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.
Formally, let the first material have strength X=x1x2…xn , and the second material have strength Y=y1y2…yn . Then the strength of the weapon is calculated as ∣x1−y1∣+∣x2−y2∣+…+∣xn−yn∣ . If the integers have different lengths, then the shorter integer is padded with leading zeros.
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.
An integer C=c1c2…ck is defined as an integer obtained by sequentially writing the digits c1,c2,…,ck from left to right, i.e. 10k−1⋅c1+10k−2⋅c2+…+ck .
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤500 ). The description of the test cases follows.
The first line of each test case contains two integers L and R ( 1≤L≤R<10100 ) — 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.
Note that the input data may not fit into standard 32 -bit or 64 -bit integer data types.
输出格式
For each test case print one integer — the maximum possible strength of the weapon that Fedya can obtain from the given materials.
输入输出样例
输入#1
6 53 57 179 239 13 37 132228 132228 54943329752812629795 55157581939688863366 88 1914
输出#1
4 19 11 0 163 28
说明/提示
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 .
In the second test case, the maximum strength is achieved with materials with strengths 190 and 209 : ∣1−2∣+∣9−0∣+∣0−9∣=19 .
In the fourth test case, there is only one valid strength, so the answer is 0 .
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.