Problem:


Score : 400 points

Problem Statement

A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:

In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.

For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.

You are given a positive integer K. Find the K-th smallest lunlun number.

Constraints

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K

Output

Print the answer.

Sample Input 1

15

Sample Output 1

23

We will list the 15 smallest lunlun numbers in ascending order:

1,
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
21,
22,
23.

Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

Note that the answer may not fit into the 32-bit signed integer type.



Sample input:
15


Sample output:
23

Submission status: Accepted

Solution code:
lunlun = []


def dfs(x):
    lunlun.append(x)
    if x > 3234566667:
        return 0
    d = x % 10
    if d != 0:
        dfs(10*x+d-1)
    dfs(10*x+d)
    if d != 9:
        dfs(10*x+d+1)


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

lunlun.sort()
k = int(input())
print(lunlun[k-1])

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())


def generate_lunlun(x):
    d = int(x) % 10
    if d != 0:
        yield x+str(d-1)
    yield x+str(d)
    if d != 9:
        yield x+str(d+1)


d = deque([str(i) for i in range(1, 10)])
for _ in range(k):
    x = d.popleft()
    for y in generate_lunlun(x):
        d.append(y)
print(x)

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    lunlun_cnt = 0
    x = 1
    answer = 0
    while lunlun_cnt < K:
        x_is_lunlun = True
        str_x = str(x)
        length = len(str_x)
        for d in range(2, length + 1):
            # check per 2 digits
            if abs(int(str_x[d - 2]) - int(str_x[d - 1])) > 1:
                x_is_lunlun = False
                x += 10**(length - d)
                break
        if x_is_lunlun:
            lunlun_cnt += 1
            answer = x
            x += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k=int(input())
x=[i for i in range(1,10)]
for i in range(k//2):
  if x[i]%10!=0:
    x.append(10*x[i]+x[i]%10-1)
  x.append(10*x[i]+x[i]%10)
  if x[i]%10!=9:
    x.append(10*x[i]+x[i]%10+1)
print(x[k-1])

Submission status: Accepted

Solution code:
K = int(input())
import copy

present = [1,2,3,4,5,6,7,8,9]
while K >= len(present):
    K -= len(present)
    next = []
    for i in range(len(present)):
        tmp = present[i]
        r = tmp % 10
        if r != 0:
            next.append(tmp * 10 + r -1)
        next.append(tmp * 10 + r)
        if r != 9:
            next.append(tmp * 10 + r +1)
    present = next

print(present[K-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    K = int(input())
    que = deque(["1", "2", "3", "4", "5", "6", "7", "8", "9"])
    if K <= 9:
        print(que[K-1])
    else:
        K -= 9
        while K >= 0:
            v = que.popleft()
            if v[-1] != "0":
                K -= 1
                v1 = v + str(int(v[-1])-1)
                if K == 0:
                    print(v1)
                    break
                que.append(v1)
            K -= 1
            v2 = v + v[-1]
            if K == 0:
                print(v2)
                break
            que.append(v2)
            if v[-1] != "9":
                K -= 1
                v3 = v + str(int(v[-1])+1)
                if K == 0:
                    print(v3)
                    break
                que.append(v3)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())
a = [i+1 for i in range(9) ] # 生成後の値を列挙する
old_a = []

while True:
    a = list(set(a))
    if K <= len(a):
        a = sorted(a)
        break
    
    old_a = a.copy()
    for x in old_a:
        for i in range(-1,2):
            d = int(x%10) + i
            if (d < 0) or (d > 9):
                continue
            nx = x*10 + d
            a.append(nx)

print(a[K-1])

Submission status: Accepted

Solution code:
k=int(input())
from collections import deque
l=deque([1,2,3,4,5,6,7,8,9])
a=0
for _ in range(k):
  a=l.popleft()
  if a%10==0:
    l.append(a*10)
    l.append(a*10+1)
  elif a%10==9:
    l.append(a*10+8)
    l.append(a*10+9)
  else:
    l.append(a*10+a%10-1)
    l.append(a*10+a%10)
    l.append(a*10+a%10+1)
print(a)

Submission status: Accepted

Solution code:
from collections import deque
K=int(input())
d = deque([1,2,3,4,5,6,7,8,9])
i=0
while 1:
  i+=1
  a=d.popleft()
  if i==K:
    print(a);exit()
    
  b=a%10
  if b==0:
    d.append(int(str(a)+"0"))
    d.append(int(str(a)+"1"))
  elif b==9:
    d.append(int(str(a)+"8"))
    d.append(int(str(a)+"9"))
  else:
    d.append(int(str(a)+str(b-1)))
    d.append(int(str(a)+str(b)))
    d.append(int(str(a)+str(b+1)))

Submission status: Accepted

Solution code:
k=int(input())
list=[1,2,3,4,5,6,7,8,9]
for i in range(k-1):
  m=list[i]
  n=m*10+m%10
  if m%10!=0:
    list.append(n-1)
  list.append(n)
  if m%10!=9:
    list.append(n+1)
print(list[k-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import queue

def solve(K: int):
    q = queue.Queue()
    # initialize
    for i in range(1, 10):
        q.put(i)
    
    for i in range(K):
        res = q.get()
        first = res % 10
        if first == 0:
            q.put(res * 10 + first)
            q.put(res * 10 + first + 1)
        elif first == 9:
            q.put(res * 10 + first - 1)
            q.put(res * 10 + first)
        else:
            q.put(res * 10 + first - 1)
            q.put(res * 10 + first)
            q.put(res * 10 + first + 1)

    print(res)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

K=int(input())
Q=queue.Queue()
for i in range(1,10):
    Q.put(i)

for i in range(1,K+1):
    deq=Q.get()
    mod=deq%10
    if mod!=0:
        Q.put(10*deq+mod-1)
    Q.put(10*deq+mod)
    if mod!=9:
        Q.put(10*deq+mod+1)
print(deq)

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
d = deque()
for i in range(1,10):
    d.append(i)
for i in range(k):
    x = d.popleft()
    m = 10*x+x%10
    if x%10!=0:
        d.append(m-1)
    d.append(m)
    if x%10!=9:
        d.append(m+1)
else:
    print(x)

Submission status: Accepted

Solution code:
K = int(input())
import queue
q = queue.Queue()
for i in range(1,10):
    q.put(i)

for i in range(K-1):
    num = q.get()
    if num%10!=0:
        q.put(10*num+(num%10)-1)
    q.put(num*10+(num%10))
    if num%10!=9:
        q.put(10*num+(num%10)+1)
    
        
print(q.get())

Submission status: Accepted

Solution code:
from queue import Queue
from sys import stdin, stdout

def check(arr):
    a = int(''.join(str(each) for each in arr))
    if a < 10:
        return True
    for i in range(1,len(arr)):
        if abs(arr[i] - arr[i - 1]) > 1:
            return False
    return True

arr = [0] * 10

arr[9] = 1
k = 0
limit = int(stdin.readline().strip())

for aa in range(0, 10):
    if aa == 0:
        brange = range(0, 10)
    else:
        brange = range(max(0, aa - 1), min(10, aa + 2))
    for bb in brange:
        if aa+bb == 0:
            crange = range(0, 10)
        else:
            crange = range(max(0, bb - 1), min(10, bb + 2))
        for cc in crange:
            if aa+bb+cc == 0:
                drange = range(0, 10)
            else:
                drange = range(max(0, cc - 1), min(10, cc + 2))
            for dd in drange:
                if aa+bb+cc+dd == 0:
                    erange = range(0, 10)
                else:
                    erange = range(max(0, dd - 1), min(10, dd + 2))
                for ee in erange:
                    if aa+bb+cc+dd+ee == 0:
                        frange = range(0, 10)
                    else:
                        frange = range(max(0, ee - 1), min(10, ee + 2))
                    for ff in frange:
                        if aa+bb+cc+dd+ee+ff == 0:
                            grange = range(0, 10)
                        else:
                            grange = range(max(0, ff - 1), min(10, ff + 2))
                        for gg in grange:
                            if aa+bb+cc+dd+ee+ff+gg == 0:
                                hrange = range(0, 10)
                            else:
                                hrange = range(max(0, gg - 1), min(10, gg + 2))
                            for hh in hrange:
                                if aa+bb+cc+dd+ee+ff+gg+hh == 0:
                                    irange = range(0, 10)
                                else:
                                    irange = range(max(0, hh - 1), min(10, hh + 2))
                                for ii in irange:
                                    if aa+bb+cc+dd+ee+ff+gg+hh+ii == 0:
                                        jrange = range(0, 10)
                                    else:
                                        jrange = range(max(0, ii - 1), min(10, ii + 2))
                                    for jj in jrange:
                                        k += 1
                                        # arr = [aa, bb, cc, dd, ee, ff, gg, hh, ii, jj]
                                        # num = int(''.join(str(each) for each in arr))
                                        # stdout.writelines("%d," % num)
                                        if k > limit:
                                            arr = [aa, bb, cc, dd, ee, ff, gg, hh, ii, jj]
                                            num = int(''.join(str(each) for each in arr))
                                            stdout.writelines("%d\n" % num)
                                            exit(0)

Submission status: Accepted

Solution code:
"""
解説見た
"""
from queue import Queue

q = Queue()

for i in range(1, 10):
    q.put(i)

k = int(input())

for i in range(k - 1):
    buf = q.get()
    if buf % 10 != 0:
        q.put(10 * buf + (buf % 10) - 1)
    q.put(10 * buf + buf % 10)
    if buf % 10 != 9:
        q.put(10 * buf + buf % 10 + 1)

print(q.get())

Submission status: Accepted

Solution code:
def f(n, d, s, k):
    if d == 0:
        k -= 1
        if k == 0:
            print(s)
            exit(0)
        return k

    if n - 1 >= 0:
        k = f(n - 1, d - 1, s + (n - 1) * (10 ** (d - 1)), k)

    k = f(n, d - 1, s + (n) * (10 ** (d - 1)), k)

    if n + 1 <= 9:
        k = f(n + 1, d - 1, s + (n + 1) * (10 ** (d - 1)), k)
    return k


k = input()
k = int(k)

l = [1, 2, 3, 4, 5, 6, 7, 8, 9]

if k <= 9:
    print(k)
    exit(0)

k = k - 9

for i in range(1, 100000):
    for j in l:
        k = f(j, i, j * (10 ** i), k)

Submission status: Accepted

Solution code:
import queue as qu

k = int(input())

q = qu.Queue()

for i in range(1,10):
    q.put(i)

for i in range(k-1):
    x = q.get(i)
    if x%10 != 0:
        q.put(10*x +x%10 -1)
    q.put(10*x +x%10)
    if x%10 != 9:
        q.put(10*x +x%10 +1)

print(q.get())

Submission status: Accepted

Solution code:
import heapq

k = int(input())
i=0
lunlun = [1,2,3,4,5,6,7,8,9]
heapq.heapify(lunlun)

while True:
    i += 1
    if i == k:
        break
    x = heapq.heappop(lunlun)
    if x % 10 != 0:
        heapq.heappush(lunlun,10 * x + (x % 10) -1)
    heapq.heappush(lunlun,10 * x + (x % 10))
    if x % 10 != 9:
        heapq.heappush(lunlun,10 * x + (x % 10) +1)

print(lunlun[0])

Submission status: Accepted

Solution code:
from collections import deque
k=int(input())
li=deque([i for i in range(1,10)])
cnt=9
if k<=cnt:print(k)
else:
    while cnt<k:
        v=li.popleft()
        if v%10==0:
            li.append(v*10)
            li.append(v*10+1)
            cnt+=2
        elif v%10==9:
            li.append(v*10+8)
            li.append(v*10+9)
            cnt+=2
        else:
            r=v%10
            li.append(v*10+r-1)
            li.append(v*10+r)
            li.append(v*10+r+1)
            cnt+=3
    print(li[k-cnt-1])

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
lun = deque([i for i in range(1, 10)])
cnt = 0
while cnt < n:
    cnt += 1
    a = lun.popleft()
    if a % 10 != 0:
        lun.append(10*a + a % 10 - 1)
    lun.append(10*a + a % 10)
    if a % 10 != 9:
        lun.append(10*a + a % 10 + 1)
print(a)

Submission status: Accepted

Solution code:
from collections import deque


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    K = read_int()
    if K < 10:
        return K
    Q = deque(range(1, 10))
    counter = 10
    while True:
        num = Q.popleft()
        digit = num%10
        for d in range(-1, 2):
            if 0 <= digit+d < 10:
                if counter == K:
                    return num*10+digit+d
                counter += 1
                Q.append(num*10+digit+d)


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
k = int(input())
l = [0 for x in range(100005)]
for i in range(10):
	l[i] = i+1
temp = 0
i = 9
while i < k:
	if l[temp] % 10 == 9:
		l[i] = l[temp] * 10 + 8
		l[i+1] = l[temp] * 10 + 9 
		i+=2
	elif l[temp] % 10 == 0:
		l[i] = l[temp] * 10
		l[i+1] = l[temp] * 10 + 1
		i+=2
	else:
		l[i] = l[temp] * 10 + l[temp] % 10 - 1
		l[i+1] = l[temp] * 10 + l[temp] % 10
		l[i+2] = l[temp] * 10 + l[temp] % 10 + 1
		i+=3
	temp+=1
print(l[k-1])

Submission status: Accepted

Solution code:
from collections import deque
 
K = int(input())
que = deque([i for i in range(1, 10)])
lunlun = []
 
while que:
    num = que.pop()
    lunlun.append(num)
    for i in range(10):
        if abs(int(str(num)[-1]) - i) <= 1:
            cand = int(str(num) + str(i))
            if cand < 10000000000:
                que.append(cand)
 
lunlun.sort()
print(sorted(lunlun)[K - 1])

Submission status: Accepted

Solution code:
import queue

k = int(input())
q = queue.Queue()

for i in range(1,10):
    q.put(i)

count = 0
while count < k:
    num = q.get()
    num_1 = int((str(num))[-1])
    if num_1 ==0:
        q.put(num*10)
        q.put(num*10+1)
    elif num_1==9:
        q.put(num*10+num_1-1)
        q.put(num*10+num_1)
    else:
        q.put(num*10+num_1-1)
        q.put(num*10+num_1)
        q.put(num*10+num_1+1)
    count+=1
    if k==count:
        ans = num
print(ans)

Submission status: Accepted

Solution code:
from queue import deque
# import sys
# input = lambda : sys.stdin.readline().rstrip()

k = int(input())
q = deque()
for i in range(1,10):
    q.appendleft(i)
for _ in range(k):
    num = q.pop()
    n = num % 10
    if n!=0:
        q.appendleft(num*10+n-1)
    q.appendleft(num*10+n)
    if n!=9:
        q.appendleft(num*10+n+1)
print(num)

Submission status: Accepted

Solution code:
import queue
import time
import sys
input = sys.stdin.readline


def main():
    K = int(input().strip())
    que = queue.Queue()
    [que.put(i) for i in range(1, 10)]
    for _ in range(K):
        answer = que.get()
        if answer % 10 != 0:
            que.put(10*answer + answer % 10 - 1)
        que.put(10 * answer + answer % 10)
        if answer % 10 != 9:
            que.put(10*answer + answer % 10 + 1)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue
k = int(input())

if k <= 9:
    print(k)
else:
    q = queue.Queue()
    for i in range(9):
        q.put(i+1)
    for i in range(k):
        s = q.get()
        if s  % 10 == 0:
            q.put(s * 10)
            q.put(s * 10 + 1)
        elif s  % 10 == 9:
            q.put(s * 10 + 8)
            q.put(s * 10 + 9)
        else:
            t = s  % 10
            q.put(s * 10 + t - 1)
            q.put(s * 10 + t)
            q.put(s * 10 + t + 1)
    print(s)

Submission status: Accepted

Solution code:
n = int(input())
l = [_ for _ in range(1,10)]

cnt = 9
d = [-1, 0, 1]
for i in range(10**5):
    if cnt >= n: break
    for j in d:
        if 0 <= int(str(l[i])[-1]) + j <= 9:
            l.append(l[i]*10 + int(str(l[i])[-1]) + j)
            cnt += 1

print(l[n-1])

Submission status: Accepted

Solution code:
n = int(input())
l = [_ for _ in range(1,10)]

cnt = 9
for i in range(10**5):
    if cnt >= n:
        break
    if str(l[i])[-1] == '0':
        l.append(l[i]*10 + int(str(l[i])[-1]))
        l.append(l[i]*10 + int(str(l[i])[-1]) + 1)
        cnt += 2

    elif str(l[i])[-1] == '9':
        l.append(l[i]*10 + int(str(l[i])[-1]) - 1)
        l.append(l[i]*10 + int(str(l[i])[-1]))
        cnt += 2

    else:
        l.append(l[i]*10 + int(str(l[i])[-1]) - 1)
        l.append(l[i]*10 + int(str(l[i])[-1]))
        l.append(l[i]*10 + int(str(l[i])[-1]) + 1)
        cnt += 3

print(l[n-1])

Submission status: Accepted

Solution code:
n = int(input())
l = [_ for _ in range(1,10)]

for i in range(10**5):
    if str(l[i])[-1] == '0':
        l.append(l[i]*10 + int(str(l[i])[-1]))
        l.append(l[i]*10 + int(str(l[i])[-1]) + 1)

    elif str(l[i])[-1] == '9':
        l.append(l[i]*10 + int(str(l[i])[-1]) - 1)
        l.append(l[i]*10 + int(str(l[i])[-1]))

    else:
        l.append(l[i]*10 + int(str(l[i])[-1]) - 1)
        l.append(l[i]*10 + int(str(l[i])[-1]))
        l.append(l[i]*10 + int(str(l[i])[-1]) + 1)

print(l[n-1])

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
LunLun = []
Q = deque()
dx = (-1, 0, 1)
for i in range(1, 10):
    LunLun.append(i)
    Q.append(i)

while len(LunLun) <= K:
    x = Q.popleft()
    y = x % 10
    for i in range(3):
        nx = y + dx[i]
        if (nx >= 0) and (nx <= 9):
            Q.append(10 * x + nx)
            LunLun.append(10 * x + nx)

print(LunLun[K-1])

Submission status: Accepted

Solution code:
import sys
from collections import deque
K = int(sys.stdin.readline().rstrip())
A = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
d = [-1, 0, 1]

for i in range(K):
    N = str(A.popleft())
    for i in d:
        if 0 <= int(N[-1]) + i <= 9:
            new = N + str(int(N[-1]) + i)
            A.append(int(new))
print(N)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from collections import deque

def rec(n, k, ans):
    print(ans)
    ans.append(int(k))
    if len(k) >= n:
        return
    d = int(k[-1])
    if d > 0:
        rec(n, k + str(d-1), ans)
    rec(n, k + str(d), ans)
    if d < 9:
        rec(n, k + str(d+1), ans)

def main():
    n = int(input().strip())
    # v = list(map(int, input().strip().split()))
    # ans = []
    # for j in range(13):
    #     for i in range(1, 10):
    #         rec(j, str(i), ans)
    # print(ans)
    c = 0
    q = deque()
    for i in range(1, 10):
        q.append(str(i))
    while len(q) > 0:
        d = q.popleft()
        c += 1
        if c == n:
            print(d)
            return
        if int(d[-1]) > 0:
            q.append(d + str(int(d[-1])-1))
        q.append(d + d[-1])
        if int(d[-1]) < 9:
            q.append(d + str(int(d[-1])+1))
    # for i in range(1, 7):
    #     ans = []


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
d = deque([i for i in range(1,10)])

count = 0
while True:
    num = d.popleft()
    count += 1
    if count == k:
        break
    str_num = str(num)
    next_digit_ls = [int(str_num[-1]) - 1, int(str_num[-1]), int(str_num[-1]) + 1]
    for digit in next_digit_ls:
        if 0<= digit <= 9:
            d.append(int(str_num + str(digit)))
print(num)

Submission status: Accepted

Solution code:
k=int(input())
if k<=9:
    print(k)
    exit()
a=[1,2,3,4,5,6,7,8,9]
cnt=9
while True:
    q=[]
    for i in a:
       for j in range(10):
            if abs(int(str(i)[-1])-j)<=1:
                cnt+=1
                if cnt==k:
                    print(int(str(i)+str(j)))
                    exit()
                q.append(int(str(i)+str(j)))         
    a=list(sorted(set(q)))

Submission status: Accepted

Solution code:
k = int( input() )

lunlun_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def lunlun_maker( lun_num, lun_list ):
    if lun_num % 10 == 0:
        lun_list.append( lun_num * 10  )
        lun_list.append( lun_num * 10 + 1 )
    elif lun_num % 10 == 9:
        lun_list.append( lun_num * 10 + 8 )
        lun_list.append( lun_num * 10 + 9 )
    else:
        lun_list.append( lun_num * 10 + ( lun_num % 10 - 1 ) )
        lun_list.append( lun_num * 10 + ( lun_num % 10 ) )
        lun_list.append( lun_num * 10 + ( lun_num % 10 + 1 ) )

i = 0
while len( lunlun_numbers ) < 100000:
    lunlun_maker( lunlun_numbers[i], lunlun_numbers )
    i += 1

print( lunlun_numbers[ k - 1 ] )

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    k = int(input())
    dq = deque()
    for i in range(1,10):
        dq.append(i)
    
    for i in range(k):
        lnln = dq.popleft()
        r = lnln%10
        if r not in (0,9):
            dq.extend([lnln*10+r-1,lnln*10+r,lnln*10+r+1])
        elif r == 9:
            dq.extend([lnln*10+r-1,lnln*10+r])
        else:
            dq.extend([lnln*10+r,lnln*10+r+1])

    print(lnln)
main()

Submission status: Accepted

Solution code:
K = int(input())

def dfs(val, digit, all):

    all.append(val)

    if digit == 10:
        return

    for i in range(-1, 2):
        add = val % 10 + i
        if 0 <= add <= 9:
            dfs(val*10 + add, digit+1, all)

all = []

for i in range(1, 10):
    dfs(i, 1, all)

all.sort()

print(all[K-1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

q = deque([])

for i in range(1, 10):
    q.append(i)

for i in range(k-1):
    a = q.popleft()
    if a % 10 != 0:
        q.append(10 * a + (a % 10) - 1)
    q.append(10 * a + (a % 10))
    if a % 10 != 9:
        q.append(10 * a + (a % 10) + 1)

print(q.popleft())

Submission status: Accepted

Solution code:
n=int(input())
if 1<=n and n<=9:
    print(n)
else:
    import queue
    q=queue.Queue()
    for i in range(1,10):
        q.put(i)
    count=9
    while count<n:
        t=q.get()
        if t%10==0:
            q.put(10*t)
            q.put(10*t+1)
            count+=2
        elif t%10==9:
            q.put(10*t+8)
            q.put(10*t+9)
            count+=2
        else:
            q.put(10*t+t%10-1)
            q.put(10*t+t%10)
            q.put(10*t+t%10+1)
            count+=3
    if count-n==0:
        if t%10!=9:
            print(10*t+t%10+1)
        else:
            print(10*t+9)
    elif count-n==1:
        if t%10!=9:
            print(10*t+t%10)
        else:
            print(10*t+8)
    else:
        print(10*t+t%10-1)

Submission status: Accepted

Solution code:
from queue import Queue
K=int(input())

q = Queue()

for i in range(1,10):
  q.put(i)
  
for n in range(K):
  if n==K-1:
    print(q.get())
  num=q.get()
  if num%10 !=0:
    q.put(10*num+(num%10)-1)
  q.put(10*num+num%10)
  
  if num%10 !=9:
    q.put(10*num+(num%10)+1)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

k = i()
lunlun_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
tmp_list = lunlun_list
tmp_tmp_list = []
cnt = 9
def lunlun(y):
    x = y[-1]
    if x == "0":
        tmp_tmp_list.append(y + "0")
        tmp_tmp_list.append(y + "1")
        return 2
    elif x == "9":
        tmp_tmp_list.append(y + "8")
        tmp_tmp_list.append(y + "9")
        return 2
    else:
        x = int(x)
        tmp_tmp_list.append(y + str(x - 1))
        tmp_tmp_list.append(y + str(x))
        tmp_tmp_list.append(y + str(x + 1))
        return 3

while len(lunlun_list) < k:
    for tmp in tmp_list:
        cnt += lunlun(str(tmp))
        if cnt >= k:
            break
    tmp_list = tmp_tmp_list
    lunlun_list += tmp_list
    tmp_tmp_list = []

lunlun_list = [int(i) for i in lunlun_list]
lunlun_list.sort()

print(lunlun_list[k - 1])

Submission status: Accepted

Solution code:
import queue
k = int(input())

q = queue.Queue()
for i in range(1,10):
    q.put(i)

for i in range(k):
    x = q.get()
    if i == k-1:
        break
    else:
        if not x % 10 == 0:
            q.put(10*x + (x % 10) -1)
        q.put(10*x + (x % 10))
        if not x % 10 == 9:
            q.put(10*x + (x % 10) +1)

print(x)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    K = int(input())
    if K <= 10:
        print(K)
        exit()

    q = deque(range(1, 10))
    K -= 9
    while q:
        v = q.popleft()
        sv = v % 10
        for i in (-1, 0, 1):
            if 0 <= sv + i < 10:
                if K == 1:
                    print(v * 10 + sv + i)
                    exit()
                K -= 1
                q.append(v * 10 + sv + i)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())

lunlun = deque([1,2,3,4,5,6,7,8,9])

p = 0

def generate_lunlun(p):
    last = p%10
    if last-1>=0:
        yield p*10+last-1
    yield p*10+last
    if last < 9:
        yield p*10+last+1

cnt = 1

while cnt < k:
    for i in generate_lunlun(lunlun.popleft()):
        lunlun.append(i)
    cnt += 1
print(lunlun[0])

Submission status: Accepted

Solution code:
k = int(raw_input())

import collections
q = collections.deque(range(1,10))


h = {u:[u-1,u,u+1] for u in range(1,9)}
h[9] = [8,9]
h[0] = [0,1]

while(k):
	u = q.popleft()
	k -=1
	if k == 0: break
	ld = u % 10
	for delta in h[ld]: q.append(u*10 + delta)
print u

Submission status: Accepted

Solution code:
K = int(input())
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(0, K):
    if A[i]%10 != 0:
        A.append(10*A[i]+A[i]%10-1)
    A.append(10*A[i]+A[i]%10)
    if A[i]%10 != 9:
        A.append(10*A[i]+A[i]%10+1)
    if len(A) >= K:
        break
print(A[K-1])

Submission status: Accepted

Solution code:
def main():
    N = int(input())  # 文字列または整数(一変数)

    l = [1, 2, 3, 4, 5, 6, 7, 8, 9]


    for i in l:
        last_digit = i % 10
        num_str = str(i)
        if last_digit != 0: l.append(int(num_str + str((last_digit-1)%10)))
        l.append(int(num_str + str((last_digit)%10)))
        if last_digit != 9: l.append(int(num_str + str((last_digit+1)%10)))
        if len(l) > N: break

    print(l[N-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue

K = int(input())

Q = queue.Queue()
for i in range(1, 10):
    Q.put(i)

for i in range(K-1):
    x = Q.get()
    if x%10 != 0:
        Q.put(10*x+x%10-1)
    Q.put(10*x+x%10)
    if x%10 != 9:
        Q.put(10*x+x%10+1)
print(Q.get())

Submission status: Accepted

Solution code:
a=int(input())
l=[[0]*10 for _ in range(10)]
l[0]=[1]*10
for i in range(1,10):
    for j in range(10):
        if j!=9 and j!=0:
            l[i][j]=l[i-1][j-1]+l[i-1][j]+l[i-1][j+1]
        elif j==0:
            l[i][j]=l[i-1][j]+l[i-1][j+1]
        else:
            l[i][j]=l[i-1][j-1]+l[i-1][j]
count=0
i=0
while count<a:
    count+=sum(l[i])-l[i][0]
    i+=1
i-=1
count-=sum(l[i])-l[i][0]
j=1
while count<a:
    count+=l[i][j]
    j+=1
j-=1
count-=l[i][j]
k=a-count
ll=[j]
jj=j
for ii in range(i):
    if jj!=0:
        jj-=1
        while k>0:
            k-=l[i-ii-1][jj]
            jj+=1
        jj-=1
        k+=l[i-ii-1][jj]
        ll.append(jj)
    else:
        while k>0:
            k-=l[i-ii-1][jj]
            jj+=1
        jj-=1
        k+=l[i-ii-1][jj]
        ll.append(jj)
        
for jjj in ll:
    print(jjj,end='')

Submission status: Accepted

Solution code:
import sys
from collections import deque

if __name__ == "__main__":
    k = int(input())

    d = deque()

    for i in range(1, 10):
        d.appendleft(i)
    
    ans = 0

    for _ in range(k):
        ans = d.pop()

        if ans % 10 != 0:
            d.appendleft(10 * ans + ans % 10 - 1)
        d.appendleft(10 * ans + ans % 10)
        if ans % 10 != 9:
            d.appendleft(10 * ans + ans % 10 + 1)
    print(ans)

Submission status: Accepted

Solution code:
import queue
q = queue.Queue()
for i in range(1,10):
    q.put(i)
K = int(input())

for k in range(K):
    x = q.get()  # dequeue
    last  = x % 10  # 一桁目を取り出す
    if last != 0:  # １桁目が0以外
        q.put(10*x + last - 1)
    q.put(10*x + last)
    if last != 9:  # １けた目が9以外
        q.put(10*x + last + 1)

print(x)

Submission status: Accepted

Solution code:
k = int(input())

import queue

q = queue.Queue()

for i in range(1, 10):
    q.put(i)
    
c = 0

while c < k:
    x = q.get()
    
    r = x%10
    
    if r!=0 and r!=9:
        q.put(10*x+r-1)
        q.put(10*x+r)
        q.put(10*x+r+1)
        c += 1
    elif r==0:
        q.put(10*x)
        q.put(10*x+1)
        c+=1
    elif r==9:
        q.put(10*x+r-1)
        q.put(10*x+r)
        c+=1
    if c==k:
        print(x)

Submission status: Accepted

Solution code:
import queue

k = int(input())

q = queue.Queue()

for i in range(1,10):
    q.put(i)
    
c = 0
while c<k:
    x = q.get()
    r = x%10
    if r != 0 and r != 9:
        q.put(10*x+r-1)
        q.put(10*x+r)
        q.put(10*x+r+1)
        c = c+1
    if r == 0:
        q.put(10*x)
        q.put(10*x+1)
        c = c+1
    if r == 9:
        q.put(10*x+r-1)
        q.put(10*x+r)
        c = c+1
    if c == k:
        print(x)

Submission status: Accepted

Solution code:
K=int(input())
# K=15
lun=list(range(1,10))
i=0
while 1:
    ichi=lun[i]%10
    if ichi!=0:
        lun.append(lun[i]*10+ichi-1)
    lun.append(lun[i]*10+ichi)
    if ichi!=9:
        lun.append(lun[i]*10+ichi+1)
    i+=1
    if i==K:
        break
print(lun[i-1])