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:
def examA():
    X, Y, Z = LI()
    X, Y = Y,X
    X,Z = Z, X
    print(X,Y,Z)
    return

def examB():
    N, M = LI()
    A = LI()
    need = (sum(A)-1)//(4*M) + 1
    ans = 0
    #print(need)
    for a in A:
        if a>=need:
            ans += 1
    if ans>=M:
        print("Yes")
    else:
        print("No")
    return

def examC():
    N, K = LI()
    ans = N%K
    if K-ans<ans:
        ans = K-ans
    print(ans)
    return

def examD():
    def bfs(n):
        # 点の数、スタートの点、有向グラフ
        W = [""] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        que = deque()
        for i in range(1,10):
            que.append(str(i))
            W[i-1] = str(i)
        i = 9
        while(i<n):
            now = que.popleft()
            end = now[-1]
            for j in [-1,0,1]:
                ne = int(end)+j
                if 0<=ne<=9:
                    W[i] = now + str(ne)
                    que.append(W[i])
                    i += 1
                    if i==n:
                        break
        return W
    K = I()
    if K<=12:
        ans = K
        print(ans)
        return
    ans = bfs(K)[-1]
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

Solution code:
def main():
    k = int(input())

    def runrun(n):
        n = list(map(int, list(str(n))))
        for i in range(len(n)-1):
            if abs(n[i] - n[i+1]) > 1:
                if n[i] > n[i+1]:
                    n[i+1] = n[i]-1
                    for j in range(i+2, len(n)):
                        n[j] = 0
                else:
                    n[i] = n[i+1]-1
                    for j in range(i+1, len(n)):
                        n[j] = 0
                return int("".join(list(map(str, n))))
        return False

    run = []
    i = 1
    cnt = 0
    while cnt < k:
        j = runrun(i)
        if j:
            i = j
        else:
            run.append(i)
            cnt += 1
            i += 1
    print(run[k-1])


main()

Submission status: Accepted

Solution code:
K = int(input())
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
cnt = 0
while len(A) < 100000:
  n = len(A)
  for i in range(cnt, cnt + n):
    x = A[i] % 10
    A.append(int(str(A[i])+str(x)))
    if x > 0:
      A.append(int(str(A[i])+str(x-1)))
    if x <= 8:
      A.append(int(str(A[i])+str(x+1)))
  cnt += n
A.sort()
print(A[K-1])

Submission status: Accepted

Solution code:
buf = [str(i) for i in range(1,10)]
next = []
ans = []
flag = False
k = int(input())

while True:
    next = []
    if flag:
        break
    for b in buf:
        ans.append(int(b))
        if b[0] == "4" and len(b) >= 10:
            flag = True
            break
        if b[-1] == "0":
            next.append(b+"0")
            next.append(b+"1")
        elif b[-1] == "9":
            next.append(b+"8")
            next.append(b+"9")
        else:
            base = int(b[-1])
            for i in range(3):
                next.append(b+str(base+i-1))
    buf = next

ans.sort()
print(ans[k-1])

Submission status: Accepted

Solution code:
k = int(input())

ans = []
r = [str(i) for i in range(1, 10)]
ans.extend(r)
for _ in range(9):
    rn = []
    for i in r:
        x = int(i[-1])
        if x == 0:
            rn.append(i+str(x+1))
            rn.append(i+str(x))
        elif x == 9:
            rn.append(i+str(x))
            rn.append(i+str(x-1))

        else:
            rn.append(i+str(x+1))
            rn.append(i+str(x))
            rn.append(i+str(x-1))
    ans.extend(rn)
    r = rn[:]

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

print(ans[k-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

K = int(input())

lis = [0]

def pl(now,keta):
    now[keta] += 1

    if keta == len(now)-1:
        if now[keta] == 10:
            now.append(1)
            now[keta] = 0
            return
        else:
            return

    else:
        if now[keta] == 10 or now[keta] > now[keta+1] + 1:
            pl(now,keta+1)
            now[keta] = max(0,now[keta+1] - 1)
            return
        else:
            return

for loop in range(K):

    pl(lis,0)

lis.reverse()
print ("".join(map(str,lis)))

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline


K = int(readline())

q = deque()

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

count = 0
while True:
    a = q.popleft()
    count += 1
    if count == K:
        ans = a
        break
    tail = a[-1]
    if tail >= 1:
        q.append(a + [tail - 1])
    q.append(a + [tail])
    if tail <= 8:
        q.append(a + [tail + 1])

print(''.join(map(str, ans)))

Submission status: Accepted

Solution code:
k = int(input())
dp = [[] for i in range(1000)]
dp[0] = list(range(1,10))
D = [-1,0,1]

count = 0
for i in range(10**5):
  count = len(dp[i])
  if count > k:
    ans = dp[i]
    ans.sort()
    print(ans[k-1])
    exit()
  else:
    k -= count
    for j in dp[i]:
      str_j = str(j)
      for d in D:
        nxt = int(str_j[-1])+d
        if 0<=nxt<=9:
          dp[i+1].append(j * 10 + nxt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 * 10 ** 5)
k = int(input())

r = []

MAX = 3234566667

def dfs(x):
    s = str(x)
    r.append(x)
    last = int(s[-1])
    for i in range(last-1, last+2):
        if 0 <= i <= 9:
            next = int(s + str(i))
            if next <= MAX:
                dfs(next)

dfs(1)
dfs(2)
dfs(3)
dfs(4)
dfs(5)
dfs(6)
dfs(7)
dfs(8)
dfs(9)

r.sort()
print(r[k-1])

Submission status: Accepted

Solution code:
import heapq

k = int(input())
ln = [i for i in range(1, 10)]
heapq.heapify(ln)
i = 0
while True:
    i += 1
    x = heapq.heappop(ln)
    if i == k:
        break
    msd = x % 10
    if msd != 0:
        heapq.heappush(ln, x * 10 + msd - 1)
    heapq.heappush(ln, x * 10 + msd)
    if msd != 9:
        heapq.heappush(ln, x * 10 + msd + 1)
print(x)

Submission status: Accepted

Solution code:
k=int(input())
ans=set([1,2,3,4,5,6,7,8,9])
for _ in range(11):
  c=set()
  for b in ans:
    x=int(str(b)[-1])
    if x==0:
      c.add(int(str(b)+'0'))
      c.add(int(str(b)+'1'))
    elif x==9:
      c.add(int(str(b)+'9'))
      c.add(int(str(b)+'8'))
    else:
      c.add(int(str(b)+str(x+1)))
      c.add(int(str(b)+str(x)))
      c.add(int(str(b)+str(x-1)))
  ans=ans|c
ans=list(ans)
ans.sort()
print(ans[k-1])

Submission status: Accepted

Solution code:
k = int(input())

lunlun = [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 + 1 <= 9:
        yield p * 10 + last + 1

while len(lunlun) < k:
    for new_lunlun in generate_lunlun(lunlun[p]):
        lunlun.append(new_lunlun)
    p += 1

print(lunlun[k-1])

Submission status: Accepted

Solution code:
K = int(input())

ans = [[] for _ in range(12)]
ans2 = [1,2,3,4,5,6,7,8,9]
ans[0] = [1,2,3,4,5,6,7,8,9]
count = 9

for i in range(12):
    if i == 0:
        pass
    else:
        for j in ans[i-1]:
            k = int(str(j)[-1])
            if k == 0:
                ans[i].append(j * 10 + k)
                ans[i].append(j * 10 + k + 1)
                ans2.append(j * 10 + k)
                ans2.append(j * 10 + k + 1)
                count += 2
            elif k == 9:
                ans[i].append(j * 10 + k - 1)
                ans[i].append(j * 10 + k)
                ans2.append(j * 10 + k - 1)
                ans2.append(j * 10 + k)
                count += 2
            else:
                ans[i].append(j * 10 + k - 1)
                ans[i].append(j * 10 + k)
                ans[i].append(j * 10 + k + 1)
                ans2.append(j * 10 + k - 1)
                ans2.append(j * 10 + k)
                ans2.append(j * 10 + k + 1)
                count += 3

            if count >= K:
                print(ans2[K-count-1])
                exit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k=int(input())
ans=[]
p=[i for i in range(1,10)]
for _ in range(9):
    q=[]
    for x in p:
        y=x%10
        q.append(x*10+y)
        if y<9: q.append(x*10+y+1)
        if y>0: q.append(x*10+y-1)
    for x in p:
        ans.append(x)
    p=[q[i] for i in range(len(q))]

for x in q:
    ans.append(x)

ans=sorted(ans)
print(ans[k-1])

Submission status: Accepted

Solution code:
k = int(input())
ans = [1,2,3,4,5,6,7,8,9]
cnt = 0
def lunlun(a,cnt):
  if cnt == 10:
    return a
  else:
    cnt += 1
    x = a%10
    for i in x-1,x,x+1:
      if 0 <= i <= 9:
        ans.append(a*10+i)
        lunlun(a*10+i,cnt)
for i in range(1,10):
  lunlun(i,0)
ans.sort()
print(ans[k-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
k = int(input())

ansl = []

def dfs(s):
    if len(s) >= 11:
        return
    ansl.append(s)
    if s[-1] != "0":
        dfs(s+str(int(s[-1])-1))
    dfs(s + str(int(s[-1])))
    if s[-1] != "9":
        dfs(s + str(int(s[-1]) + 1))

for i in range(1,10):
    dfs(str(i))
ansl = [int(a) for a in ansl]
ansl = sorted(ansl)
print(ansl[k-1])

Submission status: Accepted

Solution code:
#D
from collections import deque
K=int(input())
lunlun=[str(i) for i in range(1,10)]
Q=deque([str(i) for i in range(1,10)])
while len(lunlun)<=2*(10**5):
    q=Q.popleft()
    i=int(q[-1])
    lunlun.append(q+str(i))
    Q.append(q+str(i))
    if i+1<10:
        lunlun.append(q+str(i+1))
        Q.append(q+str(i+1))
    if i-1>=0:
        lunlun.append(q+str(i-1))
        Q.append(q+str(i-1))
lunlun=list(int(i) for i in set(lunlun))
lunlun.sort()
print(lunlun[K-1])

Submission status: Accepted

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

K = int(input())

def dfs(le, L, ret):
    if len(L) == le:
        ret.append(L)
        return ret
    l = L[-1]
    for num in range(max(0, l-1), min(l+1, 9)+1):
        ret = dfs(le, L+[num], ret)
    return ret

le = 0
ans = []
while True:
    le += 1
    for n in range(1, 10):
        ret = dfs(le, [n], [])
        if len(ret) < K:
            K -= len(ret)
        else:
            ans = ret[K-1]
            break
    if ans: break

print("".join([str(a) for a in ans]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

K = int(input())

cnt = 0
def dfs(keta, cur) :
  if keta == 0 :
    global cnt
    cnt += 1
    if cnt == K :
      print(cur)
      exit()
    return 
      
  i = cur % 10
  if i - 1 >= 0 :
    dfs(keta - 1, cur * 10 + i - 1)
  dfs(keta - 1, cur * 10 + i)
  if i + 1 <= 9 :
    dfs(keta - 1, cur * 10 + i + 1)

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

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

todo = deque(list(map(str, range(1, 10))))
count = 0
while todo:
    num = todo.popleft()
    count += 1
    if count == k:
        print(num)
        exit()

    base = int(num[-1])
    n1 = base - 1
    if n1 != -1:
        todo.append(num + str(n1))
    n2 = base
    todo.append(num + str(n2))

    n3 = base + 1
    if n3 != 10:
        todo.append(num + str(n3))

Submission status: Accepted

Solution code:
X = [[i for i in range(1, 10)]]
for i in range(9):
    Y = []
    for x in X[-1]:
        s = x % 10
        if s == 0:
            Y.append(x * 10 + s)
            Y.append(x * 10 + s + 1)
        elif s == 9:
            Y.append(x * 10 + s - 1)
            Y.append(x * 10 + s)
        else:
            Y.append(x * 10 + s- 1)
            Y.append(x * 10 + s)
            Y.append(x * 10 + s + 1)
    X.append(Y)
XX = []
for x in X:
    XX += x[:]
XX = sorted(XX)
print(XX[int(input()) - 1])

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    K=I()
    L=[]
    import queue
    
    
    q=queue.Queue()
    for i in range(1,10):
        q.put(i)
        
    dx=[-1,0,1]
        
        
    while len(L)!=K:
        a=q.get()
        L.append(a)
        res=a%10
        for i in range(3):
            c=dx[i]
            res2=res+c
            if res2!=-1 and res2!=10:
                new=a*10+res2
                q.put(new)
                
    print(L[-1])
                

main()

Submission status: Accepted

Solution code:
n = int(input())
now = [i+1 for i in range(9)]
ans = now[:]
for k in range(11):
  last = now
  now = []
  for x in last:
    y = x % 10
    if y == 0:
      now.append(x*10+y)
      now.append(x*10+y+1)
      ans.append(x*10+y)
      ans.append(x*10+y+1)
    elif y == 9:
      now.append(x*10+y-1)
      now.append(x*10+y)
      ans.append(x*10+y-1)
      ans.append(x*10+y)
    else:
      now.append(x*10+y-1)
      now.append(x*10+y)
      now.append(x*10+y+1)
      ans.append(x*10+y-1)
      ans.append(x*10+y)
      ans.append(x*10+y+1)
print(ans[n-1])
#print(ans)

Submission status: Accepted

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

LIST=[]

def next(L):
    if len(L)==10:
        return
    t=int(L[-1])
    for x in [t-1,t,t+1]:
        if 0<=x<=9:
            y=L+(x,)
            LIST.append(y)
            next(y)

for i in range(1,10):
    x=(i,)
    LIST.append(x)
    next(x)

        
L2=[]

for l in LIST:
    L2.append(int("".join(map(str,l))))

L2.sort()
print(L2[int(input())-1])

Submission status: Accepted

Solution code:
K = int(input())
if K < 10:
	print(K)
	exit()
L = [1,2,3,4,5,6,7,8,9]
k = 9
i = 0
while k < K:
	l = L[i]
	a = l % 10
	if a > 0:
		L.append(l*10 + a - 1)
		k += 1
	L.append(l*10 + a)
	k += 1
	if a < 9:
		L.append(l*10 + a + 1)
		k += 1
	i += 1
print(L[K-1])

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    K = int(input())
    ans = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    que = deque(ans)
    for _ in range(9):
        que_new = deque()
        while que:
            i = que.popleft()
            i_ = i%10
            i_new = i*10+i_
            if i_ != 0:
                ans.append(i_new-1)
                que_new.append(i_new-1)
            ans.append(i_new)
            que_new.append(i_new)
            if i_ != 9:
                ans.append(i_new + 1)
                que_new.append(i_new + 1)
        que = que_new
    print(ans[K-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

runrun = [None for _ in range(100)]
runrun[1] = (1, 2, 3, 4, 5, 6, 7, 8, 9)


def gen_runrun_keta(k):
    for x in runrun[k - 1]:
        r = x % 10
        if r > 0:
            yield 10 * x + (r - 1)
        yield 10 * x + r
        if r < 9:
            yield 10 * x + (r + 1)


for keta in range(2, 11):
    runrun[keta] = tuple(gen_runrun_keta(keta))


rest = int(read())

answer = 0
for n in range(1, 11):
    if rest <= len(runrun[n]):
        answer = runrun[n][rest - 1]
        break
    rest -= len(runrun[n])
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15


def main():
    n = getN()
    ans = 0
    runruns = [[str(i) for i in range(10)]]
    for digit in range(9):
        tmp = []
        for i in range(10):
            stri = str(i)
            for run in runruns[-1]:
                if abs(i - int(run[0])) <= 1:
                    tmp.append(stri + run)

        tmp.sort()
        runruns.append(tmp)
    runruns = [[r for r in run if r[0] != "0"] for run in runruns]
    # print(sum([len(run) for run in runruns]))
    # print(runruns[-2])
    ans = []
    for run in runruns:
        ans = ans + run

    print(ans[n-1])
    # print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a = []

def dfs(x):
    if x > 3234566667:
        return
    a.append(x)
    for i in range(10):
        if abs(x%10-i) <= 1:
            dfs(x*10+i)

for i in range(1, 10):
    dfs(i)
a = sorted(a)
k = int(input())
print(a[k-1])

Submission status: Accepted

Solution code:
import sys
import itertools

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

K = ni() - 1

for le in range(1, 11):
    for h in range(1, 10):
        for a in itertools.product((-1, 0, 1), repeat=le-1):
            cur = h
            ok = True
            for u in a:
                cur += u
                if cur > 9 or cur < 0:
                    ok = False
                    break
            if ok:
                if K == 0:
                    ret = [h] + [_ + h for _ in itertools.accumulate(a)]
                    print("".join(map(str, ret)))
                    sys.exit(0)
                K -= 1

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def li(i):
        if i == 0:
            return [0,1]
        if i < 9:
            return [i-1,i,i+1]
        else:
            return [8,9]

    f = [(i,i) for i in range(1,10)]
    s = 10
    while len(f) < 10**5:
        nf = [(i*10+k,k) for (i,j) in f[-s:] for k in li(j)]
        f += nf
        s = len(nf)
    k = I()
    print(f[k-1][0])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
k = int(input())
s = list(range(1, 10))
l = []
while s:
    p = s.pop()
    l.append(p)
    n = p % 10
    for d in range(max(0, n - 1), min(10, n + 2)):
        if p * 10 + d <= 3234566667:
            s.append(p * 10 + d)
l.sort()
print(l[k - 1])

Submission status: Runtime Error

Solution code:
from collections import deque
K = int(input())
queue = deque([1,2,3,4,5,6,7,8,9])
count = 1
while count <= K:
  num = queue.popleft()
  if num%10!=0:
    queue.append(num*10+num%10-1)
  queue.append(num*10+num%10)
  if num%!=9:
    queue.append(num*10+num%10+1)
  
print(num)

Submission status: Runtime Error

Solution code:
from collections import deque

K = int(input())

count = 0
ans = 0
Q = deque([1,2,3,4,5,6,7,8,9])
while count != K:
  a = Q.popleft()
  b = a%10
  if b != 0:
    Q.append(q*10 + b - 1)
  Q.append(q*10)
  if b != 9:
    Q.append(q*10 + b + 1)
  count += 1
  ans = q
print(q)

Submission status: Runtime Error

Solution code:
def update_queue(queue):
    out = queue.pop(0)
    mod10 = out % 10
    if mod10 != 0:
        queue.append(10 * out + mod10 - 1)
    queue.append(10 * queue + mod10)
    if mod10 != 9:
        queue.append(10 * out + mod10 + 1)

    return out, queue

N = int(input())
Q = [1,2,3,4,5,6,7,8,9]

for _ in range(N):
    out, Q = update_queue(Q)

print(out)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
lst = list(map(int,input().split()))
s = 0
total = sum(lst)
for i in range(n):
  if lst[i] >= total/(4*m):
    s += 1
    
if s >= m:
  print('Yes')
else:
  print('No')

Submission status: Runtime Error

Solution code:
t

Submission status: Runtime Error

Solution code:
que = queue.Queue()

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

for i in range(1, k + 1):
    ans = que.get()
    keta1 = ans % 10
    if keta1 == 0:
        append_list = [ans * 10, ans * 10 + 1]
    elif keta1 == 9:
        append_list = [ans * 10 + 8, ans * 10 + 9]
    else:
        append_list = [ans * 10 + keta1 - 1, ans * 10 + keta1, ans * 10 + keta1 + 1]
    for item in append_list:
        que.put(item)
print(ans)

Submission status: Runtime Error

Solution code:
def f(a, d, n):

    if n == 0:
        fans = ''
        for i in range(d):
            fans = fans + str(max(0, int(a) - i))

    else:
        s = f(a, d, n - 1)
        k = 0
        for j in range(d - 1):
            if s[d - 2 - j] >= s[d - 1 - j]:
                k = d - 1 - j
                break

        t = f(str(int(s[d - 1 - j]) + 1), j + 1, 0)
        fans = s[:k] + t
    
    return fans

lnln = [[0] * 10 for _ in range(10 + 1)]
lnln[1] = [1] * 10

for i in range(2, 10 + 1):
    for j in range(10):
        if j == 0:
            lnln[i][0] = lnln[i - 1][0] + lnln[i - 1][1]
        elif j == 9:
            lnln[i][9] = lnln[i - 1][8] + lnln[i - 1][9]
        else:
            lnln[i][j] = lnln[i - 1][j - 1] + lnln[i - 1][j] + lnln[i - 1][j + 1]

N = int(input())
S = 0
ok = False
for i in range(1, 10 + 1):
    for j in range(1, 10):
        if S + lnln[i][j] >= N:
            d, a, n = i, j, N - S - 1
            ok = True
            break
        else:
            S += lnln[i][j]
    if ok == True:
        break

ans = int(f(str(a), d, n))

print(ans)

Submission status: Runtime Error

Solution code:
def main():
  N, K, C=map(int, input().split())
  S = input()
  
  S=S[::-1]
  R=set()
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      R.add(N-n)
      k+=1
      n += C
    n+=1
  #print(R)
  
  S=S[::-1]
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      if n+1 in R:
        print(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  

  
if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
K=int(input())

p=1
dp,old=[[1]*10],[0,1]
n=9
while K>n:
  old=dp[p-1]
  tmp=[0]*10
  for i in range(1,9):
    tmp[i]=old[i-1]+old[i]+old[i+1]
  tmp[9]=old[8]+old[9]
  tmp[0]=old[0]+old[1]
  dp.append(tmp)
  p+=1
  n+=sum(tmp[1:])

ans=0
n-=sum(tmp[1:])
K-=n
c=2
for i in range(p-1,-1,-1):
  if c!=0:
    c-=1
  while K>dp[i][c]:
    K-=dp[i][c]
    c+=1
  ans+=c*10**i
print(ans)

Submission status: Runtime Error

Solution code:
k=int(input())
L=[]
def f(d,now,L):
  L.append(now)
  
  if d==10:
    return
  
  for j in range(-1,2):
    v=now%10+j
    if 0<=v<=9:
      f(d+1,now*10+v,L)

f(0,0,L)
print(L[k-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import log10,ceil
def main():
    k = int(input())
    k2 = ceil(k / 10)
    def getlun(n):
        lunluns.append(n)
        ns = str(n)
        print(lunluns)
        if len(ns) > k2:
            pass
        else:
            ns1 = int(ns[0])
            if ns1 != 0:
                l1 = ns[0] + ns
                getlun(int(l1))
            if ns1 > 1:
                l2 = str(ns1 - 1) + ns
                getlun(int(l2))
            if ns1 < 9:
                l3 = str(ns1 + 1) + ns
                getlun(int(l3))
    lunluns = []
    for i1 in range(0, 10):
        getlun(i1)
    lunluns.sort()
    print(lunluns[k])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections

def main():
    k = int(input())
    Q = collections.deque([int(i) for i in range(1, 10)])
    for i in range(k):
        x = Q.popleft()
        if i + len(Q) < k:
            if x%10:
                Q.append(10*x + x%10 - 1)
            Q.append(10*x + x%10)
            if x%10 != 9:
                Q.append(10*x + x%10 + 1)
        print(Q)
    print(x)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def binary_search_int(ok, ng, solve):
    """
    :param ok: solve(x) = True を必ず満たす点
    :param ng: solve(x) = False を必ず満たす点
    """
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok, ng

##############################################################

def solve(x):
    """ ある点 x を境にして True と False が二分されるような関数"""
    return N - K*x >= 0

N, K = map(int, input().split())

a, b = binary_search_int(0, 10**18, solve)
print(min(abs(N-a*K), abs(N-b*K)))

Submission status: Runtime Error

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 + l[i][-1] + j)
            cnt += 1

print(l[n-1])

Submission status: Runtime Error

Solution code:
def incr_lunlun(num):
    num[0] += 1
    if len(num) == 1:
        if num[0] == 10:
            num.append(1)
            num[0] = 0

    elif num[0] > num[1] + 1 or num[0] == 10:
        suffix = incr_lunlun(num[1:])
        num = [suffix[0] - 1] + list(suffix)

    return num


def main():
    k = int(input())
    num = [1]
    for i in range(k-1): 
        num = incr_lunlun(num)

    print(int(''.join(str(i) for i in reversed(num))))



main()

Submission status: Runtime Error

Solution code:
from numba import jit

@njit
def resolve():
	from collections import deque
	K = int(input())
	q = deque(str(i) for i in range(1, 10))
	cnt = 9
	if K < 10:
		print(K); return
	while True:
		tmp = q.popleft()
		las = int(tmp[-1])
		for i in range(las-1, las+2):
			if 0<=i<=9:
				q.append(tmp + str(i))
				cnt += 1
				if cnt==K:
					print(q.pop()); return
resolve()

Submission status: Runtime Error

Solution code:
from collections import deque
K = int(input())
q = deque(str(i) for i in range(1, 10))
cnt = 9
if K < 10:
    print(K); return
while True:
    tmp = q.popleft()
    las = int(tmp[-1])
    for i in range(las-1, las+2):
        if 0<=i<=9:
            q.append(tmp + str(i))
            cnt += 1
            if cnt==K:
                print(q.pop()); return

Submission status: Runtime Error

Solution code:
k = int(input())
L = []

def lunlun(d,v,L):
    L.append(v)
    if d == 4:
        return
    for i in range(-1,2):
        t = v%10 + i
        #print(v)
        if 0 <= t <=9:
            lunlun(d+1,v*10+t,L)
#lunlun(1,1,L)
for v in range(1,10):
    lunlun(1,v,L)
print(sorted(L)[k-1])

Submission status: Runtime Error

Solution code:
n=int(input())
from collections import deque
q=deque([])
i=0
while True:
  if i<=8:
    q.append(i+1)
    i+=1
    if i==k:break
    continue
  
  x=q.popleft()
  
  if x%10!=0:
    q.append(x*10+x%10-1)
    i+=1
    if i==k:break
    
  q.append(x*10+x%10)
  i+=1
  if i==k:break
  
  if x%10!=9:
    q.append(x*10+x%10+1)
    i+=1
    if i==k:break
      
print(q.pop())

Submission status: Runtime Error

Solution code:
i

Submission status: Runtime Error

Solution code:
K=int(input())

limit=10**6 #実行時間オーバーにならないように数値を調整したい
lunlun_number_list=[1,2,3,4,5,6,7,8,9,10,11,12]

for i in range(13,limit): #i=152
    flag=1 #ルンルン数なら1が立つ
    num1=i%10 #num1=2
    tmp=i-num1 #tmp=150
    while tmp >= 10:
        tmp//=10 #tmp=15 ⇒ tmp=1
        num2=tmp%10  #num2=5 ⇒ num2=1
        if abs(num1-num2) > 1:
            flag=0
            break
        else:
            pass
    if flag == 1:
        lunlun_number_list.append(int(i))
#print(lunlun_number_list)

#print(len(lunlun_number_list))

print(lunlun_number_list[int(K)-1])

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

n=int(input())
L=deque(list(range(1,10)))
if n<=9:
    ans = L[n-1]
else:
    cnt = 9
    for i in range(1,n):
        c=L.popleft()
        
        if c%10!=0:
            L.append(c*10+(c%10)-1)
            cnt+=1
            if cnt>=n:
                break
        L.append(c*10+(c%10))
        cnt+=1
        if cnt>=n:
            break
        
        if c%10!=9:
            L.append(c*10+(c%10)+1)
            cnt+=1
            if cnt>=n:
                break
        print(L)
    ans = L[-1]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
b=int(input())
if b==100000:
  print(3234566667)
  sys.exit()
L=[1,2,3,4,5,6,7,8,9,10,11,12,21,22,23]
for i in range(30,10**5*5):
  a=0
  c=str(i)
  t=list(c)
  for j in range(len(c)-1):
    if abs(int(t[j+1])-int(t[j]))<=1:
      a+=1
  if a==len(c)-1:
    L.append(i)
  if len(L)>=b:
    break
print(L[b-1])

Submission status: Runtime Error

Solution code:
from collections import deque
que=deque([i for i in range(1,10)])
k=int(input())
count=0
while count!=k-1:
  a=que.popleft()
  count+=1
  if a%10==1:
    que.extend([10*a+1,10*a+2])
  elif a%10==9:
    que.extend([10*a+8,10*a+9])
  else:
    b=a*10+(a%10)-1
    que.extend([b,b+1,b+2])
print(a)

Submission status: Runtime Error

Solution code:
from collections import deque
que=deque([i for i in range(1,10)])
k=int(input())
count=0
while count!=k:
  a=que.popleft()
  count+=1
  if a%10 == 1:
    que.append([10*a+1,10*a+2])
  elif a%10==9:
    que.append([10*a+8,10*a+9])
  else:
    b=a*10+(a%10)-1
    que.append([b,b+1,b+2])
print(count)