Adjacent Digits Differ by 2+

Difficulty: 1900 4000 ms 128 MB

digit-dp

Count integers in [L, R] where every pair of adjacent digits differs by at least 2.

Input: one line with two integers L and R.

Output: the count in [L, R].

Constraints:

• 1 ≤ L ≤ R ≤ 10¹⁸

Sample Tests

1 30

24

40 90

36

Read the Editorial