Overview

For integers from \(1\) to \(N\), we count how many have the property that the absolute difference between “the sum of digits at odd positions from the left” and “the sum of digits at even positions from the left” is at most \(D\), using Digit DP.

Analysis

Key Insight

For an integer \(d_1d_2\ldots d_k\): - \(S_{\mathrm{odd}} = d_1 + d_3 + \cdots\) - \(S_{\mathrm{even}} = d_2 + d_4 + \cdots\)

So the difference [ S{\mathrm{odd}} - S{\mathrm{even}} ] can be treated as a cumulative sum where we add \(+d\) for odd-positioned digits from the left and \(-d\) for even-positioned digits.

In other words, when determining digits from left to right, all we need to track is “how many digits have been determined so far” and “what is the current difference.”

Why a Brute Force Approach Won’t Work

Since \(N \le 10^{15}\), we would need to enumerate up to \(10^{15}\) numbers, and even computing digit sums for each would be far too slow (TLE).

How to Solve It

We efficiently count only the numbers satisfying the condition using “Digit DP,” which determines digits from left to right.

Furthermore, the constraint “at most \(N\)” can be handled using the standard technique: - Numbers with fewer digits than \(N\) can be freely enumerated (without leading zeros) - Numbers with the same number of digits as \(N\) require tracking whether we are still at the upper bound (tight) or not

Algorithm

Let the difference be defined as: [ \Delta = S{\mathrm{odd}} - S{\mathrm{even}} ]

1. Count all integers with \(L\) digits (\(L < \mathrm{len}(N)\))

Define the DP as: - \(dp[\Delta] =\) “the number of ways to determine digits up to position pos from the left such that the difference equals \(\Delta\)”

When choosing digit \(d\) at position pos: - If pos is odd (1, 3, 5, …): \(\Delta \leftarrow \Delta + d\) - If pos is even (2, 4, 6, …): \(\Delta \leftarrow \Delta - d\)

For the leading digit, \(d \in \{1,\dots,9\}\); for all other positions, \(d \in \{0,\dots,9\}\).

Finally, sum up the counts for all \(\Delta\) satisfying \(|\Delta| \le D\).

2. Count numbers with the same number of digits as \(N\) that are \(\le N\) (tight / loose)

Let digs be the digits of \(N\), and split the state into two types:

• tight[Δ]: the count when the prefix so far exactly matches \(N\)
• loose[Δ]: the count when the prefix is already confirmed to be smaller than \(N\)

At position pos, the upper bound for digit selection is: - From tight: \(0 \sim \text{limit}\) (but \(1 \sim \text{limit}\) for the leading digit) - From loose: \(0 \sim 9\) (but \(1 \sim 9\) for the leading digit)

When choosing digit \(d\) from tight: - If \(d = \text{limit}\), the next state remains tight - If \(d < \text{limit}\), it transitions to loose

This is the standard Digit DP transition.

Finally, summing up entries from both tight and loose where \(|\Delta| \le D\) gives the answer for “same number of digits and \(\le N\).”

3. Array Indexing for Difference \(\Delta\) (offset)

Since \(\Delta\) can be negative, we shift it for array indexing: [ \text{index} = \Delta + \text{offset} ] (In the code, offset=200, size=401.)
Since the number of digits is at most around \(16\), and the absolute value of the difference is at most \(9 \times 16 = 144\), this range is more than sufficient.

Complexity

Let \(R\) (here \(401\)) be the range of possible values of \(\Delta\). Since we make 10 transitions per digit:

• Time complexity: \(O(\mathrm{len}(N) \cdot R \cdot 10)\)
  (The part for \(L < \mathrm{len}(N)\) also exists, but since \(\mathrm{len}(N) \le 16\), it is of the same order)
• Space complexity: \(O(R)\)

Implementation Notes

• Prohibit 0 for the leading digit: Managed with start_d = 1 if pos == 1 else 0.

• Odd positions get +, even positions get -: Since we count from the left, we determine sign using pos % 2.

• Managing \(\le N\) with tight / loose: This is the standard technique for accurately counting numbers that “do not exceed the upper bound” among those with the same length.

• Use offset to store negative differences in an array: Start with dp[offset] = 1 as the initial state (difference of 0).

  Source Code

import sys

def count_all_length(L: int, D: int, offset: int, size: int) -> int:
    dp = [0] * size
    dp[offset] = 1
    for pos in range(1, L + 1):
        ndp = [0] * size
        sign = 1 if (pos % 2 == 1) else -1
        start_d = 1 if pos == 1 else 0
        for idx, val in enumerate(dp):
            if val == 0:
                continue
            for d in range(start_d, 10):
                nidx = idx + sign * d
                if 0 <= nidx < size:
                    ndp[nidx] += val
        dp = ndp
    lo = max(0, offset - D)
    hi = min(size - 1, offset + D)
    return sum(dp[lo:hi + 1])

def count_upto_same_length(digs, D: int, offset: int, size: int) -> int:
    L = len(digs)
    tight = [0] * size
    loose = [0] * size
    tight[offset] = 1

    for pos in range(1, L + 1):
        limit = digs[pos - 1]
        sign = 1 if (pos % 2 == 1) else -1
        start_d = 1 if pos == 1 else 0

        ntight = [0] * size
        nloose = [0] * size

        # From tight state
        for idx, val in enumerate(tight):
            if val == 0:
                continue
            for d in range(start_d, limit + 1):
                nidx = idx + sign * d
                if 0 <= nidx < size:
                    if d == limit:
                        ntight[nidx] += val
                    else:
                        nloose[nidx] += val

        # From loose state
        for idx, val in enumerate(loose):
            if val == 0:
                continue
            for d in range(start_d, 10):
                nidx = idx + sign * d
                if 0 <= nidx < size:
                    nloose[nidx] += val

        tight, loose = ntight, nloose

    lo = max(0, offset - D)
    hi = min(size - 1, offset + D)
    return sum(tight[lo:hi + 1]) + sum(loose[lo:hi + 1])

def main():
    N_str = sys.stdin.readline().strip()
    D = int(sys.stdin.readline().strip())

    digs = list(map(int, N_str))
    LN = len(digs)

    offset = 200
    size = 401

    ans = 0
    for L in range(1, LN):
        ans += count_all_length(L, D, offset, size)
    ans += count_upto_same_length(digs, D, offset, size)

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.