Problem 529165 · hard · Phase 05 Advanced Algorithms & Graphs

Prize Tickets on a Giant Roll

digit dynamic programming · modular arithmetic · counting · prefix differences

A fairground prints one ticket for every whole number from lo to hi inclusive. A ticket wins a prize when the sum of the decimal digits of its number is a multiple of k. The number 0 has digit sum 0, which counts as a multiple. Return how many tickets on the roll win.

Examples

Input:  lo = 1, hi = 30, k = 5
Output: 5
Explanation: 5, 14, 19, 23 and 28 have digit sums 5, 5, 10, 5 and 10.

Input:  lo = 0, hi = 20, k = 10
Output: 2
Explanation: 0 (digit sum 0) and 19 (digit sum 10).

Constraints

  • 0 <= lo <= hi <= 10**18
  • 1 <= k <= 100
  • The roll can hold about 10**18 tickets, so they cannot be checked one by one.

Goals

  • Turn a range count into two counts from zero with f(hi) - f(lo - 1)
  • Count numbers up to N digit by digit, separating the tight prefix from the free ones
  • Keep only the digit sum modulo k as DP state
Starting Python…