Шифровка

시간 제한2초메모리 제한1024 MB

요약
무한 문자열 1234567891011...의 부분 문자열 [l, r]이 주어질 때, 그 안에 온전히 들어가는 자연수의 개수를 구한다.
난이도

보통10점 중 6점

유형
수학, 이분 탐색, 구현
정답자
아직 제출이 없습니다

문제

Источник, пожелавший остаться неизвестным, прислал Дэдпулу зашифрованное сообщение, в котором сообщались возможные координаты базы противника. Возможные координаты представляли собой отрезок натуральных чисел от x_1x\_1 до x_2x\_2 включительно. Шифровалось сообщение довольно простым способом: берется последовательность десятичных записей всех натуральных чисел, записанных подряд без пропусков (1234567891011121314...1234567891011121314...) и сообщается ее подотрезок \[l,r]\[l, r], отвечающий за числа с x_1x\_1 по x_2x\_2 включительно. Например, если x_1=1,x_2=6x\_1=1, x\_2=6, зашифрованное сообщение будет выглядеть так: \[1,6]\[1, 6]. А если x_1=11,x_2=14x\_1=11, x\_2=14, то так: \[12,19]\[12, 19].

Однако, получив сообщение, Дэдпул сразу понял, что оно дошло не совсем правильно, возможно, кто-то его испортил по пути. Делать нечего, поэтому теперь по данным числам ll, rr он хочет понять хотя бы примерные координаты базы: найти все натуральные числа, которые полностью входят в отрезок шифровки.

입력

В первой строке входного файла записано два числа ll, rr (1≤l≤r≤10181 \le l \le r \le 10^{18}) --- шифровка, полученная Дэдпулом.

출력

В единственной строке выходного файла выведите количество натуральных чисел, полностью содержащихся в отрезке \[l,r]\[l, r] строки <<1234567891011...>>, то есть координаты, в которых может находиться база противника. Для лучшего понимания условия смотрите примеры.

힌트

В первом тесте подходят все натуральные числа от 1 до 9.

Во втором тесте подходят только числа 8, 9, 10, 11, 12, 13. У числа 14 в данном отрезке содержится только первая его цифра, поэтому оно не учитывается.

예제2

  1. 예제 1

    입력
    1 9
    
    예상 출력
    9
    
  2. 예제 2

    입력
    8 18
    
    예상 출력
    6