Задача №115133. Максимальная прочность
Федя играет в новую игру «The Legend of Link», в которой одной из способностей персонажа является монтаж двух материалов в одно оружие. Каждый материал имеет свою прочность, которую можно обозначить целым положительным числом. Прочность полученного оружия определяется как сумма модулей разностей цифр в десятичной записи чисел на каждой позиции у двух материалов, выбранных для монтажа.
Формально, пусть первый материал имеет прочность \(X = \overline{x_{1}x_{2} \ldots x_{n}}\), а второй имеет прочность \(Y = \overline{y_{1}y_{2} \ldots y_{n}}\). Тогда прочность оружия вычисляется как \(|x_{1} - y_{1}| + |x_{2} - y_{2}| + \ldots + |x_{n} - y_{n}|\). Если числа имеют различные длины, то более короткое число дополняется ведущими нулями .
Федя имеет в своем инвентаре в неограниченном количестве материалы со всеми возможными прочностями от \(L\) до \(R\) включительно, помогите ему найти максимально возможную прочность оружия, которую он может получить, выбрав ровно \(2\) материала (возможно одинаковых) для монтажа.
Запись \(C = \overline{c_{1}c_{2} \ldots c_{k}}\) определяет число, полученное последовательной записью десятичных цифр \(c_1, c_2, \ldots, c_k\) слева направо, т.е. \(C = 10^{k-1} \cdot c_1 + 10^{k-2} \cdot c_2 + \ldots + c_k\).
В первой строке вводится число \(L\) (\(1 \le L < 10^{10^5}\)) — десятичная запись числа, обозначающая минимальную прочность материалов.
Во второй строке вводится число \(R\) (\(L \le R < 10^{10^5}\)) — десятичная запись числа, обозначающая максимальную прочность материалов.
Гарантируется, что числа \(L\) и \(R\) не содержат ведущих нулей.
Обратите внимание, что входные данные могут не помещаться в стандартные \(32\)-битные или \(64\)-битные целочисленные типы данных.
Выведите одно целое число — максимально возможную прочность оружия, которую может получить Федя из данных материалов.
В первом примере оружие, сделанное из материалов с характеристиками \(53\) и \(57\), будут иметь наибольшую прочность: \(|5 - 5| + |3 - 7| = 4\).
Во втором примере максимальная прочность достигается при материалах с характеристиками \(190\) и \(209\): \(|1 - 2| + |9 - 0| + |0 - 9| = 19\).
В третьем примере есть только одна допустимая прочность, поэтому ответ \(0\).
В пятом примере максимальная прочность достигается при материалах с прочностями \(1909\) и \(90\): \(|1 - 0| + |9 - 0| + |0 - 9| + |9 - 0| = 28\). Обратите внимание, что более короткое число было дополнено ведущими нулями.
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(R - L \le 500\) и \(R \le 10^{36}\), наберут не менее \(40\) баллов.
Решения, корректно работающие, когда первые цифры в \(L\) и \(R\) различны, наберут не менее \(20\) баллов.
Решения, корректно работающие, когда количество цифр в \(L\) строго меньше, чем количество цифр в \(R\), наберут не менее \(20\) баллов.
Дополнительно, решения, корректно работающие при \(R \le 10^{18}\) будут набирать не менее половины от указанных выше баллов. Обратите внимание, некоторые тесты могут соответствовать сразу нескольким дополнительным ограничениям.
53 57
4
179 239
19
132228 132228
0
54943329752812629795 55157581939688863366
163
88 1914
28