Гладкие числа. Python

Тут надо подумать! Я вижу один алгоритм, но что-то он мне не нравится - слишком большой перебор...

 if (l > m) return false; 

Чатгптшник этот в принципе в правильном направлении двигался. Потом съехал куда-то.

Вот его dp:

 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 

[11, 10, 9, 8, 7, 6, 5, 4, 3, 2] 

[66, 55, 45, 36, 28, 21, 15, 10, 6, 3] 

[286, 220, 165, 120, 84, 56, 35, 20, 10, 4] 

[1001, 715, 495, 330, 210, 126, 70, 35, 15, 5] 

[3003, 2002, 1287, 792, 462, 252, 126, 56, 21, 6] 

[8008, 5005, 3003, 1716, 924, 462, 210, 84, 28, 7] 

[19448, 11440, 6435, 3432, 1716, 792, 330, 120, 36, 8] 

[43758, 24310, 12870, 6435, 3003, 1287, 495, 165, 45, 9]

[92378, 48620, 24310, 11440, 5005, 2002, 715, 220, 55, 10] 

И эти числа обозначают вполне понятную вещь
dp[i][j] это количество гладких чисел используя j цифр меньших или равных i

Соответственно, количество цифр как искать очевидно.
[92378, 48620, 24310, 11440, 5005, 2002, 715, 220, 55, 10] - просто найти здесь ближайшее число

Дальше пока что думаю.

Python:

 n = int(input()) 

dp = [[0] * 10 for _ in range(11)] 

dp[0] = [1] * 10 

for i in range(1, 11): 

    for j in range(10): 

        dp[i][j] = sum(dp[i - 1][j:]) 

for i in range(1, 11): 

    for j in range(10): 

        dp[i][j] += dp[i - 1][j] 

def get_number(n): 

    if n == 1: 

        return 0 

    n -= 1 

    res = [0] * 11 

    for i in range(10, -1, -1): 

        if n >= dp[10][i]: 

            res[10] = i 

            n -= dp[10][i] 

            break 

    for i in range(9, -1, -1): 

        for j in range(res[i + 1], -1, -1): 

            if n >= dp[i][j]: 

                res[i] = j 

                n -= dp[i][j] 

                break 

    return ''.join(map(str, res)).lstrip('0') 

print(get_number(n)) 

 

C++:

 #include  

using namespace std; 

int n; 

int dp[11][10]; 

int get_number(int n) { 

    if (n == 1) { 

        return 0; 

    } 

    n--; 

    int res[11]; 

    memset(res, 0, sizeof(res)); 

    for (int i = 9; i >= 0; i--) { 

        if (n >= dp[10][i]) { 

            res[10] = i; 

            n -= dp[10][i]; 

            break; 

        } 

    } 

    for (int i = 8; i >= 0; i--) { 

        for (int j = res[i + 1]; j >= 0; j--) { 

            if (n >= dp[i][j]) { 

                res[i] = j; 

                n -= dp[i][j]; 

                break; 

            } 

        } 

    } 

    int ans = 0; 

    for (int i = 10; i >= 0; i--) { 

        ans *= 10; 

        ans += res[i]; 

    } 

    return ans; 

} 

int main() { 

    cin >> n; 

    memset(dp, 0, sizeof(dp)); 

    for (int i = 0; i < 10; i++) { 

        dp[0][i] = 1; 

    } 

    for (int i = 1; i < 11; i++) { 

        for (int j = 0; j < 10; j++) { 

            for (int k = j; k < 10; k++) { 

                dp[i][j] += dp[i - 1][k]; 

            } 

        } 

    } 

    cout

Правильный код:

def g(n):
f = [[0]*10 for _ in range(2)]
f[1] = [1]*10
m = 1
while True:
f.append([0]*10)
s = 0
for d in range(9, -1, -1):
s += f[m][d]
f[m+1][d] = s
if f[m+1][0] > n:
break
m += 1

d = 0
for k in range(m, 0, -1):
for e in range(d, 10):
if f[k][e] > n:
d = e
break
n -= f[k][e]
print(d, end='')

assert n == 0

if __name__ == "__main__":
n = int(input())
g(n)
print()