主页 / 问题 / 1417800
Accepted
Thwrani
Asked:2022-08-07 17:41:50 +0800 CST2022-08-07 17:41:50 +0800 CST

问题“平滑数字”

  • 772

如果一个数字的数字从最高有效数字开始形成一个非递减序列，我们就称它为平滑数字。按升序对所有这些数字进行排序，并为每个数字分配一个数字。需要输出第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）

python c++

2 个回答

  1. Best Answer

    例子：

    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

    第 th 个数字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++ 实现更简单、更短，但我错了。用 values 填充数组更容易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
    • 4

  2. 评论建议生成平滑的数字。
    我想出了这个选项：

    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)

    但是运行太慢了

    • 0

相关问题