아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Gleb and Two Numbers

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

요약
l과 r이 아주 긴 십진수 문자열로 주어질 때, [l, r] 구간에서 두 정수의 해밍 거리(자릿수가 다른 개수)의 최댓값을 구한다.
난이도

보통10점 중 5점

유형
문자열, 그리디, 수학, 구현
정답자
아직 제출이 없습니다

문제

When Gleb is not busy with writing long problem statements he enjoys playing with numbers. He picks two integers ll and rr and tries to find integers aa and bb such that l≤a≤b≤rl \le a \le b ≤ r and the Hamming distance between aa and bb is maximum possible.

The Hamming distance between two integers xx and yy is defined as the number of decimal places at which they are different. If these integers are of different length, the shorter one is prepended with leading zeroes.

입력

The first line of the input contains a single integer ll and the second line contains a single integer rr (1≤l≤r≤101,000,0001 \leq l \leq r \leq 10^{1\\,000\\,000}).

출력

Print the maximum possible Hamming distance between a pair of integers in range from ll to rr.

힌트

In the first sample, one can choose integers 1212 and 1616. In the second sample, 11 and 1010 form an optimal answer.

예제2

  1. 예제 1

    입력
    11
    17
    
    예상 출력
    1
    
  2. 예제 2

    입력
    1
    11
    
    예상 출력
    2