Overview

This problem asks us to count the integers from \(1\) to \(N\) where the absolute difference between the sum of digits at odd-positioned places \(S_{\mathrm{odd}}\) and the sum of digits at even-positioned places \(S_{\mathrm{even}}\) is at most \(D\).

Since \(N\) can be as large as \(10^{15}\), a naive approach of checking each integer one by one will not be fast enough. By using digit DP (dynamic programming), where we determine digits from the most significant to the least significant while being aware of the upper bound \(N\), we can solve this efficiently.

---

Analysis

1. Why doesn’t a naive search work?

If we iterate through all integers from \(1\) to \(N\) and check each integer’s digits, we would need up to \(10^{15}\) iterations in the worst case. Since a typical computer can perform roughly \(10^8\) operations per second, this brute-force approach would exceed the time limit (TLE).

2. Solving with Digit DP

For problems that count integers satisfying conditions like “integers at most \(N\),” the approach of “determining digits one by one from the most significant digit” is extremely effective. This is digit DP.

However, in this problem, we need to pay attention to the following two points.

① Handling Leading Zeros

For example, when the total number of digits is \(5\), suppose we represent the number 123 as 00123. If we count the leading 0s as-is, we get 0 (1st position, odd), 0 (2nd position, even), 1 (3rd position, odd), 2 (4th position, even), 3 (5th position, odd), making 1 an odd-positioned digit. Originally, the odd-positioned digits of 123 are 1 and 3, and the even-positioned digit is 2. Thus, to correctly determine “which position a digit is at since the number actually started,” we need to distinguish between the state “the number hasn’t started yet (all 0s)” and “the number has already started.”

② State of Odd or Even Position

When the number has started, depending on whether the current digit being determined is at an “odd position” or “even position,” we either add the digit to the difference (add to \(S_{\mathrm{odd}}\)) or subtract it (add to \(S_{\mathrm{even}}\), i.e., subtract from the difference). Therefore, we need to maintain the parity of the current digit position as a state.

③ Difference Management and Offset

We maintain the difference \(S_{\mathrm{odd}} - S_{\mathrm{even}}\) between the sum of odd-positioned digits and the sum of even-positioned digits as a DP state. Since \(N \le 10^{15}\), the maximum number of digits is \(15\). Each digit is at most \(9\), so the maximum difference is \(15 \times 9 = 135\) and the minimum is \(-135\). Since negative numbers cannot be used as array indices, by adding a base value (offset) of about \(150\), we can safely manage the difference as a non-negative integer in the range \([0, 300]\).

---

Algorithm

DP State Definition

When determining each digit from the top, we maintain the following states:

• is_less: Whether the value being constructed is confirmed to be less than \(N\) (0: not confirmed, 1: confirmed)
• is_started: Whether a digit of \(1\) or greater has already appeared, meaning the number representation has begun (0: not started, 1: started)
• parity: What position (counting from the start) the next digit to be determined is (0: odd position, 1: even position)
• diff: The current value of “sum of odd-positioned digits - sum of even-positioned digits” plus the offset (\(150\))

We update the state dp[is_less][is_started][parity][diff] combining all of these.

State Transitions

We determine the next digit \(d\) (\(0 \le d \le 9\)) from the most significant digit downward.

1. When the number hasn’t started yet (is_started == 0)

   • When \(d = 0\): The number still hasn’t started. The state doesn’t change, and diff remains the same.
   • When \(d > 0\): The number starts here. This becomes the “1st (odd-positioned)” digit, so we add \(d\) to diff, and the next digit becomes “even-positioned (parity = 1)”. Also, is_started changes to 1.

2. When the number has already started (is_started == 1)

   • When parity == 0 (next digit is odd-positioned): Add \(d\) to diff, and the next digit becomes “even-positioned (parity = 1)”.
   • When parity == 1 (next digit is even-positioned): Subtract \(d\) from diff, and the next digit becomes “odd-positioned (parity = 0)”.

Final Aggregation

After all digits have been determined, the answer is the sum of states satisfying the following conditions: - is_started == 1 (it is a positive integer) - diff (after offset application) is within the allowed range of difference \(D\) (i.e., \(\mathrm{OFFSET} - D \le \mathrm{diff} \le \mathrm{OFFSET} + D\))

---

Complexity

Time Complexity

• Let \(L\) be the number of digits in \(N\) (\(1 \le L \le 15\)).
• The number of DP states is \(L \times 2 \times 2 \times 2 \times \mathrm{MAX\_DIFF}\). Here, we set \(\mathrm{MAX\_DIFF} = 301\).
• The number of transitions from each state (choices for the next digit \(d\)) is at most \(10\).
• Therefore, the overall complexity is \(O(L \times \mathrm{MAX\_DIFF} \times 10)\). When \(L = 15\), the number of operations is \(15 \times 8 \times 301 \times 10 \approx 3.6 \times 10^5\), which runs sufficiently fast (a few milliseconds) within the time limit (typically 2.0 seconds).

Space Complexity

• The DP table only needs “the state from the previous digit” when computing the next digit, so the table can be reused.
• Therefore, the required space complexity is \(O(\mathrm{MAX\_DIFF})\), consuming almost no memory.

---

Implementation Notes

1. Speedup through Encoding into a 1D Array In languages like Python, accessing multi-dimensional lists (nested lists) has significant overhead. In the solution code, the multi-dimensional state (is_less, is_started, parity, diff) is encoded into a single integer and managed as a 1D array of size STATE_SIZE, achieving dramatic speedup.

   # Map the state to a single index
   state = ((is_less * 2 + is_started) * 2 + parity) * MAX_DIFF + diff

1. Appropriate Offset Setting The minimum difference is \(-135\) and the maximum is \(135\). By setting OFFSET = 150 with some margin and MAX_DIFF = 301, all difference values are contained within non-negative indices (\([15, 285]\)).

   Source Code

import sys

def solve():
    # Read all inputs from standard input
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N_str = input_data[0]
    D = int(input_data[1])
    
    L = len(N_str)
    OFFSET = 150
    MAX_DIFF = 301
    STATE_SIZE = 2 * 2 * 2 * MAX_DIFF  # 2408 states
    
    # dp[state] where state is encoded as:
    # ((is_less * 2 + is_started) * 2 + parity) * MAX_DIFF + diff
    dp = [0] * STATE_SIZE
    
    # Initial state: is_less=0, is_started=0, parity=0, diff=OFFSET
    initial_state = ((0 * 2 + 0) * 2 + 0) * MAX_DIFF + OFFSET
    dp[initial_state] = 1
    
    for char in N_str:
        limit = int(char)
        next_dp = [0] * STATE_SIZE
        
        for is_less in range(2):
            for is_started in range(2):
                for parity in range(2):
                    base_idx = ((is_less * 2 + is_started) * 2 + parity) * MAX_DIFF
                    for diff in range(MAX_DIFF):
                        count = dp[base_idx + diff]
                        if count == 0:
                            continue
                        
                        max_d = 9 if is_less else limit
                        for d in range(max_d + 1):
                            next_is_less = is_less or (d < limit)
                            
                            if is_started == 0:
                                if d == 0:
                                    next_is_started = 0
                                    next_parity = 0
                                    next_diff = diff
                                else:
                                    next_is_started = 1
                                    next_parity = 1  # Next digit is the 2nd digit (even index)
                                    next_diff = diff + d
                            else:
                                next_is_started = 1
                                if parity == 0:  # Odd-positioned digit
                                    next_diff = diff + d
                                    next_parity = 1
                                else:  # Even-positioned digit
                                    next_diff = diff - d
                                    next_parity = 0
                            
                            next_state = ((next_is_less * 2 + next_is_started) * 2 + next_parity) * MAX_DIFF + next_diff
                            next_dp[next_state] += count
        dp = next_dp
        
    ans = 0
    # Sum up valid states where is_started = 1 and |diff - OFFSET| <= D
    for is_less in range(2):
        for parity in range(2):
            base_idx = ((is_less * 2 + 1) * 2 + parity) * MAX_DIFF
            for diff in range(OFFSET - D, OFFSET + D + 1):
                if 0 <= diff < MAX_DIFF:
                    ans += dp[base_idx + diff]
                    
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.