c++ - 计算第 n 个不包含给定数字的数字的程序

Question

我被要求编写一个 C++ 程序来计算不包含给定数字的第 n 个数字，并且执行时间小于0.1 秒。内存似乎不是问题，因为我最多可以使用 64 MB。

问题原文是这样的:

Cifra4

To represent numbers, it was decided not to use the digit C again. Thus, from the array of natural numbers, all numbers containing the digit C will be erased. Let the new array be S.

Requirements

1) Determine the N-th number in S.

2) Y and Z are two natural numbers from the array of all natural numbers. Determine the number of
natural numbers removed from Y to Z.

Input data

The input file cifra4.in contains the first number T representing the type of requirement. If T == 1, the second row will contain the digit C and the number N. If T == 2, the second line will contain the digit C and two natural numbers Yand Z.

Output data

In the output file cifra4.out will contain in the first row one natural number according to the type of requirement.

Restrictions and clarifications

1 ≤ N ≤ 10 ^ 13
0 ≤ C ≤ 9
1 ≤ Y ≤ 10 ^ 13
1 ≤ Z ≤ 10 ^ 13
for 20% of the tests, N will have a maximum of 5 digits
for 20% of the tests, Y and Z will have a maximum of 6 digits

Example 1

cifra4.in

1
0 11

cifra4.out

12

Example 2

cifra4.in

2
1 3 20

cifra4.out

10

我最好的尝试是确定(或至少应该确定)不包含数字“0”的第 n 个数字的代码，但对于 10 ^ 13 它返回 23210987654321，其中显然包含0。

我最终保留了我较慢但正确的方法。这是代码:

#include <fstream>

std::ifstream in("cifra4.in");
std::ofstream out("cifra4.out");

const long long pow_of_10[14] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000,
                                 10000000000, 100000000000, 1000000000000};

void req_1 ()
{
    short digit;
    long long n;
    in >> digit >> n;
    for (long long i = 0; i <= n; i++)
    {
        long long nr = i;
        if (nr)
        {
            long k = 1;
            do
            {
                if (nr % 10 == digit)
                {
                    n += pow_of_10[k];
                    i += pow_of_10[k] - 1;
                    break;
                }
                nr /= 10;
                k++;
            }
            while (nr);
        }
        else if (digit == 0) n++;
    }
    out << n - 1;
}

void req_2()
{
    short digit;
    long long lhs, rhs;
    long long elim = 0;
    in >> digit >> lhs >> rhs;
    for (long long i = lhs; i <= rhs; i++)
    {
        long long nr = i;
        while (nr)
        {
            if (nr % 10 == digit)
            {
                elim++;
                break;
            }
            nr /= 10;
        }
    }
    out << elim;
}

int main()
{
    short requirement;
    in >> requirement;
    if (requirement == 1)
        req_1();
    else
        req_2();
}

注意

我不一定要代码，而是要想法，可能的算法可以在适当的时间内执行多达 10 ^ 13，最好是问题要求的时间，但 1 秒对我来说就足够了。

Answer 1

假设 9 是禁用数字。在这种情况下，您只需将数字转换为 base-9 即可。

现在，当禁止数字不同时会发生什么，比如 d？它仍然是一个 9 进制数，但你必须映射你的数字，这样 d 以下的数字不受影响，d 及以上的数字映射到数字 d + 1。

例如，当禁止数字为7，n为125时。

• 第 1 步:转换为 9 进制:125₁₀ = 148₉
• 第 2 步:映射数字。 1 → 1, 4 → 4, 8 → 9

解是149。