Classy Numbers (Codeforces 1036C)
Tags: DP, combinatorics

Let's call some positive integer classy if its decimal representation contains no more than $$$3$$$ non-zero digits. For example, numbers $$$4$$$, $$$200000$$$, $$$10203$$$ are classy and numbers $$$4231$$$, $$$102306$$$, $$$7277420000$$$ are not.You are given a segment $$$[L; R]$$$. Count the number of classy integers $$$x$$$ such that $$$L \le x \le R$$$.Each testcase contains several segments, for each of them you are required to solve the problem separately.

Input: The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of segments in a testcase.Each of the next $$$T$$$ lines contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \le L_i \le R_i \le 10^{18}$$$).

Output: Print $$$T$$$ lines — the $$$i$$$-th line should contain the number of classy integers on a segment $$$[L_i; R_i]$$$.


Sample Inputs:
4
1 1000
1024 1024
65536 65536
999999 1000001

Sample Outputs:
1000
1
0
2

Solution (Python):
from functools import *
import sys
input = sys.stdin.readline
dp = [[-1] * 4 for _ in range(20)]
s = [0] * 20

def f(i, is_limit, num):
    if num > 3:
        return 0
    if i == 0:
        return 1
    if not is_limit and dp[i][num] != -1:
        return dp[i][num]
    res = 0
    up = int(s[i]) if is_limit else 9
    res = f(i - 1, is_limit and up == 0, num)
    if num != 3:
        for d in range(1, up + 1):
            res += f(i - 1, is_limit and d == up, num + 1)
    if not is_limit:
        dp[i][num] = res
    return res

def solve(x):
    n = 0
    if x == 0:
        s[1] = 0
        n = 1
    while x:
        n += 1
        s[n] = x % 10
        x //= 10
    return f(n, True, 0)
l = int(input())
for _ in range(l):
    (l, r) = map(int, input().split())
    print(solve(r) - solve(l - 1))

Solution (Python):
T = int(input())
max_nonzero = 3

def solve(pos, bound, cnt, R):
    if dp[pos][cnt] != -1 and bound == 0:
        return dp[pos][cnt]
    if cnt == 0 or pos == -1:
        return 1
    max_dig = int(R[-1 - pos]) if bound else 9
    ans = 0
    for dig in range(max_dig + 1):
        if dig != 0:
            ans += solve(pos - 1, 1 if bound and dig == max_dig else 0, cnt - 1, R)
        else:
            ans += solve(pos - 1, 1 if bound and dig == max_dig else 0, cnt, R)
    if bound == 0:
        dp[pos][cnt] = ans
    return ans
R_max = '1000000000000000000'
dp = [[-1 for _ in range(4)] for _ in range(len(R_max))]
solve(len(R_max) - 1, 1, max_nonzero, R_max)
for _ in range(T):
    (L, R) = input().split()
    y = solve(len(R) - 1, 1, max_nonzero, R)
    L = str(int(L) - 1)
    x = solve(len(L) - 1, 1, max_nonzero, L)
    print(y - x)

Solution (Python):
def classy(ran, nb):
    p = len(ran)
    if p == 0 or nb == 0:
        return 0
    elif p <= nb:
        return int(ran)
    elif nb == 0:
        return 1
    elif ran[0] == '0':
        return classy(ran[1:], nb)
    else:
        p -= 1
        k = 1
        s = 1
        for i in range(nb - 1):
            k *= (p - i) / (i + 1)
            s += k * 9 ** (i + 1)
        k *= (p - nb + 1) / nb
        s = (int(ran[0]) - 1) * s + s + k * 9 ** nb
        return s + classy(ran[1:], nb - 1)
t = int(input())
res = []
for i in range(t):
    ran = [j for j in input().split()]
    res.append(classy(ran[1], 3) - classy(str(int(ran[0]) - 1), 3))
for i in res:
    print(int(i))