Translation Notice
This article was machine-translated using DeepSeek-R1.

• Original Version: Authored in Chinese by myself
• Accuracy Advisory: Potential discrepancies may exist between translations
• Precedence: The Chinese text shall prevail in case of ambiguity
• Feedback: Technical suggestions regarding translation quality are welcomed

Original Problem Links: Luogu; AtCoder

Approach

Generate subsequent digits as (last digit -1)/last digit/(last digit +1) based on the previous digit, enqueue them, then output the K-th dequeued integer.

Notes

• Using int instead of long long will cause WA!
• When last digit is 0, next digit cannot be -1 (special case)
• When last digit is 9, next digit cannot be 10 (special case)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <cstdio>
#include <queue>
using namespace std;

typedef long long LL;

int main(int argc, char** argv)
{
    int k;
    scanf("%d", &k);
    queue<LL> q;
    for(int i=1; i<10; i++) q.push(i);
    while(true)
    {
        LL x = q.front(); q.pop();
        if(--k == 0)
        {
            printf("%lld\n", x);
            return 0;
        }
        int r = x % 10LL;
        x *= 10LL;
        x += r;
        if(r > 0) q.push(x - 1);
        q.push(x);
        if(r < 9) q.push(x + 1);
    }
    return 0;
}