Задача "Гладкие числа"

Question

Назовём число гладким, если его цифры, начиная со старшего разряда, образуют неубывающую последовательность. Упорядочим все такие числа в возрастающем порядке и присвоим каждому номер. Требуется по номеру N вывести N-е гладкое число.

1 <= N <= 2147483647

Примеры:

Ввод: 3 Вывод: 3
Ввод: 11 Вывод: 12

Я написал такой код на Python:

n = int(input())
result = ""
#В dp[i][j] записано кол-во гладких чисел длины i, начинающихся на цифру j
dp = [[0] * 10 for _ in range(n + 1)] #я немного не понял, откуда надо брать длину dp
for j in range(10):
    dp[1][j] = 1
for i in range(2, n):
    for j in range(10):
        dp[i][j] = sum(dp[i - 1][k] for k in range(10) if k >= j)
#Находим длину n-го гладкого числа
n_l = 1
for i in range(1, n):
    if dp[i + 1][0] >= n and dp[i][0] < n:
        n_l = i
        break
n -= dp[n_l][0]
#Находим первую цифру числа
j = 1
while n >= dp[n_l][j]:
    n -= dp[n_l][j]
    j += 1
result += str(j)
prev = j
#Находим оставшиеся цифры числа
if n_l > 1:
    while n > 0:
        for j in range(prev + 1, 10):
            if n <= dp[i - 1][j]:
                n -= dp[i - 1][j]
                result += str(j)
                prev = j
                break
            n -= dp[n_l - 1][j]
print(result)

Данный код работает только на маленьких значениях N. Что в нём исправить, для того, чтобы оно работало и на больших значениях N (N <= 2147483647)

Answer 1

В комментариях предлагали генерировать гладкие числа.
Я придумал такой вариант:

def f(n : str) -> str:
    if n[-1] == '9':
        if len(n) == 1:
            return str(int(n) + 2)
        tmp = f(n[:-1])
        return tmp + str(int(tmp[-1]))
    else:
        return str(int(n) + 1)

n = int(input())
result = '1'
while n > 1:
    result = f(result)
    n -= 1
print(result)

Но он работает слишком медленно

Answer 2

Пример:

7??? # сколько гладких числе имеют такой вид?
     # все они могут быть одного из видов ниже
77??
78??
79??

Если f(k, d) - число гладких чисел с цифрой d в разряде k, то f(k, d) = sum(d <= e < 10, f(k - 1, e)). Краевое условие f(1, d) = 1.

Тогда функцию f вычисляет такой код:

@functools.cache
def f(k, d):
    if k == 1:
        return 1
    return sum(f(k - 1, e) for e in range(d, 10))

С помощью функции f можно "собрать" n-ое число из цифр. Код для вычисления m - количества цифр в ответе:

    m = 1
    while f(m + 1, 0) <= n:
        m += 1

Цифры n-ого числа подбираются от старших разрядов к младшим. d - последняя подобранная цифра, k - разряд:

    d = 0
    s = 0
    for k in range(m, 0, -1):
        for d in range(d, 10):
            if s + f(k, d) > n:
                break
            s += f(k, d)
        yield d

Всё вместе:

import functools


@functools.cache
def f(k, d):
    if k == 1:
        return 1
    return sum(f(k - 1, e) for e in range(d, 10))


def g(n):
    m = 1
    while f(m + 1, 0) <= n:
        m += 1

    d = 0
    s = 0
    for k in range(m, 0, -1):
        for d in range(d, 10):
            if s + f(k, d) > n:
                break
            s += f(k, d)
        yield d
    assert s == n


print(*g(int(input())), sep='')

$ echo 3 | python nth-smooth.py 
3

$ echo 11 | | python nth-smooth.py 
12

$ echo 2147483647 | python nth-smooth.py 
11111111333333344444444444444777777778999

$ time echo 1000000000000000000000000000000000000 | python nth-smooth.py | wc -c
41468

real  0m0.927s
user  0m0.884s
sys   0m0.040s

Дополнение

Функция f(k, d), оказывается равна Cnk(k + 8 - d, 9 - d). В предыдущей реализации функцию f можно заменить на ...

def f(k, d):
    return math.comb(k + 8 - d, 9 - d)

... и будет работать быстрее. Доказательство это факта не сложно, опущу его пока. Я надеялся что прямое вычисление Cnk сделает реализацию на C++ проще и короче но ошибся. Проще заполнить массив со значениями f:

#include <cassert>
#include <iostream>
#include <vector>

void g(uint64_t n) {
    std::vector<std::vector<uint64_t>> f(1); // unused zero column/row
    f.emplace_back(10, 1);                   // f(1, d) == 1
    unsigned m = 1;
    for (; ; ) {
        f.emplace_back(10);
        uint64_t s = 0;
        for (int d = 9; d >= 0; --d) {
            s += f[m][d];
            f[m + 1][d] = s;
        }
        if (f[m + 1][0] > n) {
            break;
        }
        ++m;
    }

    unsigned d = 0;
    for (unsigned k = m; k > 0; --k) {
        for (unsigned e = d; e < 10; ++e) {
            if (f[k][e] > n) {
                d = e;
                break;
            }
            n -= f[k][e];
        }
        std::cout << d;
    }
    assert(n == 0);
}

int main() {
    uint64_t n;
    std::cin >> n;
    g(n);
    std::cout << '\n';
}

Нормально работает до числа 18348006354228436599 = Cnk(577, 9) - 1:

$ g++ -std=c++11 -pedantic -Wall -Wextra -Werror nth-smooth.cpp 

$ echo 3 | ./a.out 
3

$ echo 11 | ./a.out 
12

$ echo 2147483647 | ./a.out 
11111111333333344444444444444777777778999

$ echo 18348006354228436599 | ./a.out 
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

БЛОГ НА HUSL

Задача "Гладкие числа"

Ответы (2 шт):

Дополнение