题解 | C #找到数字# py

C #找到数字# 复杂度O(20t)

# 设首位数字a，末位z，中间部分设为b，设长度为m。
# 那么x = a * 10^(m-1) + b * 10 + z 
# f(x) = (a * 10^(m-2) + b) + (b * 10 + z) = a * 10^(m-2) + b * 11 + z
# 其中 1 <= a <= 9 , 0 <= b < 10^(m-2) , 0 <= z <= 9
# 相加得 10^(m-2) <= f(x) < 10^(m-1) + 9 (也就说明m只用枚举2个）
# 接下来只用枚举 a,m,z 求出 b 验证是否在范围内就可以了

import sys
input = sys.stdin.readline

def solve(n):
    s = str(n)
    m = len(s)
    if m == 1:
        return n
    cnt = 0
    for t in [pow(10, m - 2),pow(10, m - 1)]:
        for a in range(1, 10):
            res = n - a * t
            if res >= 0 and (res % 11) < 10 and res // 11 < t:
                cnt += 1
    return cnt
    
for _ in range(int(input())):
    n = int(input())
    print(solve(n))