A village fair prints raffle tickets numbered lo to hi (inclusive), each number written in plain decimal with no leading zeros. The printer's stamp for one digit d is almost worn out: it can print that digit at most k times on a single ticket before the ticket comes out smudged.
Implement count_tickets(lo: int, hi: int, d: int, k: int) -> int: how many ticket numbers x with lo <= x <= hi contain the digit d at most k times?
count_tickets(1, 30, 2, 0) # 18 1..30 minus {2, 12, 20, 21, ..., 29}
count_tickets(95, 105, 0, 0) # 5 95..99; 100..105 all contain a 0
count_tickets(0, 0, 0, 0) # 0 the ticket "0" uses the digit 0 once
count_tickets(1000, 1000, 0, 2) # 0 "1000" has three zeros
Constraints: 0 <= lo <= hi <= 10**18, 0 <= d <= 9, 0 <= k <= 19. The tests use ranges spanning up to 10**18 numbers, so looping over them is hopeless.
Watch out for d = 0: leading zeros are not printed, so 7 has no zeros even if you think of it as 007 while building it digit by digit. The number 0 itself is printed as a single 0.
Show hint
Write f(n) = count for 0..n and answer f(hi) - f(lo - 1). For f, build the number from the left with memoized state (position, tight, started, uses of d so far); started says whether a non-zero digit has been placed yet, and a 0 only counts toward d = 0 once the number has started.