만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

암호문

면접 대비

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

요약
자연수를 1, 2, 3 순서로 이어 붙인 문자열에서 l번째부터 r번째까지 구간에 모든 자릿수가 들어가는 수의 개수를 구합니다.
난이도

보통10점 중 5점

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

문제

익명의 정보원이 데드풀에게 적의 기지가 있을 법한 좌표가 담긴 암호문을 보냈다. 가능한 좌표는 자연수 x1x_1부터 x2x_2까지의 구간이며, 양 끝을 포함한다.

암호화 방식은 간단하다. 모든 자연수를 10진수로 표기해 공백 없이 이어 붙이면 1234567891011121314…1234567891011121314\ldots 같은 문자열이 된다. 암호문은 이 문자열에서 x1x_1부터 x2x_2까지의 수에 해당하는 부분 구간 [l,r][l, r]이다. 예를 들어 x1=1x_1=1, x2=6x_2=6이면 암호문은 [1,6][1, 6]이다. x1=11x_1=11, x2=14x_2=14이면 [12,19][12, 19]이다.

암호문은 전달 과정에서 훼손되었을 수 있다. 데드풀은 ll과 rr로 기지의 대략적인 위치를 알고 싶어 한다. 문자열 1234567891011…1234567891011\ldots의 구간 [l,r][l, r] 안에 완전히 들어가는 자연수를 모두 찾아라.

입력

첫 줄에 데드풀이 받은 암호문인 두 정수 ll, rr (1≤l≤r≤10181 \le l \le r \le 10^{18})이 주어진다.

출력

문자열 1234567891011…1234567891011\ldots의 구간 [l,r][l, r] 안에 완전히 들어가는 자연수의 개수를 한 줄에 출력한다.

힌트

첫 번째 테스트에서는 1부터 9까지 모든 자연수가 조건을 만족한다.

두 번째 테스트에서는 8, 9, 10, 11, 12, 13만 조건을 만족한다. 14는 구간에 첫 자리인 1만 들어 있으므로 세지 않는다.

예제2

  1. 예제 1

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

    입력
    8 18
    
    예상 출력
    6