def count_internal(s): if s == "-1": return 0 digits = list(map(int, s)) n = len(digits) from collections import defaultdict # DP[i][is_tight][prev_digit] = (total_count, num_count) dp = [defaultdict(lambda: defaultdict(lambda: (0, 0))) for _ in range(n + 1)] # Initialize with 0 digits, tight=True, prev_digit=None, (count=0, num=1) dp[0][True][None] = (0, 1) for pos in range(n): current_digit = digits[pos] for is_tight in [True, False]: for prev_d in list(dp[pos][is_tight].keys()): current_count, current_num = dp[pos][is_tight][prev_d] # Determine the maximum digit we can choose at current position max_d = current_digit if is_tight else 9 for d in range(0, max_d + 1): new_is_tight = is_tight and (d == max_d) # Update new_prev_d (if previous was None and this is the first digit) if prev_d is None: if d == 0 and pos == 0: # Still leading zero, prev remains None new_prev = None else: new_prev = d else: new_prev = d # Calculate additional count add_count = 0 if prev_d is not None: if prev_d == 1 and d == 2: add_count = current_num new_total_count = current_count + add_count new_num_count = current_num # Update the next state new_prev_key = new_prev entry = dp[pos + 1][new_is_tight] prev_total, prev_num = entry.get(new_prev_key, (0, 0)) entry[new_prev_key] = (prev_total + new_total_count, prev_num + new_num_count) total = 0 for is_tight in [True, False]: for key in dp[n][is_tight]: cnt, num = dp[n][is_tight][key] total += cnt return total def compute_part2(a_plus_1, b): a_plus_1 = max(a_plus_1, 1) # m must be >=1 since m >= A+1 could be 0 but m starts from 2 max_k = len(str(b)) if b !=0 else 1 total =0 for k in range(1, max_k +1): lower = 2 * 10 ** (k-1) upper = 3 * 10 ** (k-1) -1 actual_lower = max(lower, a_plus_1) actual_upper = min(upper, b) if actual_lower > actual_upper: continue # Now find the numbers between actual_lower and actual_upper with last digit 2 # and check if they start with 2 (which they do because of lower and upper) # last digit must be 2 # Compute start and end in [actual_lower, actual_upper] where last digit is 2 start = actual_lower if start %10 !=2: start = start + (2 - start %10) %10 if start < actual_lower: start +=10 if start > actual_upper: continue end = actual_upper if end %10 !=2: end = end - ( (end %10 -2) %10 ) if end < actual_lower: continue if end < start: continue # Now count the numbers from start to end inclusive with step 10 count = ((end - start) //10) +1 total += count return total def main(): A, B = map(int, input().split()) # Part 1: Internal occurrences from A to B # Compute f(B) - f(A-1) def f(x): return count_internal(str(x)) if x >=0 else 0 part1 = f(B) - f(A-1) # Part 2: m = n+1, where n is from A to B-1 inclusive, n ends with 1, m starts with 2 # m is from (A+1) to B, inclusive. m must be of form: starts with 2, ends with 2 part2 = compute_part2(A +1, B) print(part1 + part2) if __name__ == "__main__": main()