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.

Solution (Python):
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

k = ni()

luns = []


def make_lunlun(l):
    if l > 3234566667:
        return
    luns.append(l)

    last = l-l//10*10

    if last!=0:
        make_lunlun(l*10 + last-1)
    make_lunlun(l*10+last)
    if last!=9:
        make_lunlun(l*10 + last+1)


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

print(sorted(luns)[k-1])

Solution (Python):

k = int(input())
q = []

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

while True:
    if k <= len(q):
        print(q[k-1])
        break
    k = k - len(q)
    old_q = q[:]
    q = []

    for x in old_q:
        for i in range(-1, 2):
            d = x%10 + i
            if d < 0 or d > 9:
                continue
            nx = x*10 + d
            q.append(nx)

Solution (Python):
k = int(input())

a = list(range(1, 10))

while(1):
    if k <= len(a):
        print(a[k-1])
        exit()
    k -= len(a)
    old = []
    old, a = a, old
    for x in old:
        for i in [-1, 0, 1]:
            d = x%10 + i
            if d<0 or d>9: continue
            nx = x*10 + d
            a.append(nx)

Solution (Python):
k = int(input())
lunList = [i for i in range(1, 10)]
for i in range(k-9):
    x = lunList[i]
    for j in range(-1, 2):
        d = x%10 + j
        if 0 <= d <= 9:
            lunList.append(10*x + d)
print(lunList[k-1])

Solution (Python):
k = int(input())
if k<=9:
    print(k)
    exit(0)

dp = [[1]*10]
counts = [0,9]
digit = 0

while counts[-1] < k:
    digit += 1
    d = [0]*10
    d[0] = dp[-1][0] + dp[-1][1]
    for i in range(1,9):
        d[i] = dp[-1][i-1] + dp[-1][i] + dp[-1][i+1]
    d[9] = dp[-1][8] + dp[-1][9]
    dp.append(d)
    count = counts[-1]
    for i in range(1,10):
        count += d[i]
        if count >= k:
            leading = i
            print(leading, end="")
            count -= d[i]
            k -= count
            break
    counts.append(count)

digit -= 1

while digit>=0:
    d = dp[digit]
    if leading == 0:
        r = range(0,2)
    elif leading == 9:
        r = range(8,10)
    else:
        r = range(leading-1,leading+2)
    count = 0
    for i in r:
        count += d[i]
        if count >= k:
            leading = i
            print(leading, end="")
            count -= d[i]
            k -= count
            digit -= 1
            break
print("")

Solution (Python):
import collections

k = int(input())
time = 1

q = collections.deque()

q.extend([1,2,3,4,5,6,7,8,9])

while(time <= k):

    i = q.popleft()
    
    time += 1

    
    if i % 10 != 0:
        q.append(i*10 + i%10 - 1)

    
    q.append(i*10 + i%10)

    
    if i % 10 != 9:
        q.append(i*10 + i%10 + 1)

print(i)

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

q = deque([1,2,3,4,5,6,7,8,9])
ans = 0
flg = 0
cnt = 0

while(flg != 1):
    ans = q.popleft()
    cnt += 1

    tmp = ans % 10
    if tmp != 0:
        q.append(ans * 10 + tmp - 1)
    
    q.append(ans * 10 + tmp)
    
    if tmp != 9:
        q.append(ans * 10 + tmp + 1)

    if cnt == k:
        print(ans)
        flg = 1

Solution (Python):
from collections import deque
K = int(input())

q = deque([i for i in range(1, 10)])

for i in range(K):
    x = q.popleft()
    amari = x%10
    if amari == 0:
        l, m = 10*x, 10*x+1
        q.append(l)
        q.append(m)
    elif amari == 1:
        l, m, r = x*10, x*10+1, x*10+2
        q.append(l)
        q.append(m)
        q.append(r)
    elif amari == 9:
        l, m = 10*x+8, 10*x+9
        q.append(l)
        q.append(m)
    else:
        l, m, r = 10*x+(amari-1), 10*x+(amari), 10*x+(amari+1)
        q.append(l)
        q.append(m)
        q.append(r)

print(x)

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

ans = deque([i for i in range(1, 10)])


def generate_lunlun(x):
    y = x % 10
    if 0 <= y-1:
        yield 10*x + y-1
    yield 10*x + y
    if y+1 < 10:
        yield 10*x + y+1


cnt = 0
while True:
    x = ans.popleft()
    for i in generate_lunlun(x):
        ans.append(i)
    cnt += 1
    if cnt == k:
        print(x)
        break

Solution (Python):
K=int(input())
lst=[1]
qqq=0
for i in range(K-1):
    if qqq==len(lst)-1:
        if lst[qqq]<9:
            lst[qqq]+=1
            for j in range(qqq-1,-1,-1):
                lst[j]=max(0,lst[j+1]-1)
            qqq=0
        else:
            lst=[0]*len(lst)+[1]
            qqq=0
    else:
        while qqq<len(lst)-1:
            if lst[qqq]<=lst[qqq+1] and lst[qqq]<9:
                break
            qqq+=1
        if qqq==len(lst)-1 and lst[qqq]==9:
            lst=[0]*len(lst)+[1]
            qqq=0
        else:
            lst[qqq]+=1
            for j in range(qqq-1,-1,-1):
                lst[j]=max(0,lst[j+1]-1)
            qqq=0
lst=list(map(str,lst[::-1]))
print("".join(lst))

Solution (Python):
from collections import deque
K = int(input())

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

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

print(x)

Solution (Python):
from collections import deque


def main():
    K = int(input())
    queue = deque([i + 1 for i in range(9)])
    cnt = 1

    if K < 13:
        print(K)
        return

    while cnt < K:
        cnt += 1
        x = queue.popleft()
        r = x % 10

        if r != 0:
            queue.append(x*10 + r - 1)
        queue.append(x*10 + r)
        if r != 9:
            queue.append(x*10 + r + 1)

    print(queue.popleft())


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque
import sys
k=int(input())
que = deque()
count=0
for i in range(1, 10):  
    que.append(i)
    count += 1
    if count == k:
        print(que.pop())
        sys.exit()


while True:
    tmp = que.popleft()  
    tmp = tmp * 10 + tmp % 10  
    if tmp % 10 != 0:  
        que.append(tmp- 1)
        count += 1
        
        if count == k:
            break
    que.append(tmp)
    count += 1
    
    if count == k:
        break
    if tmp % 10 != 9:
        que.append(tmp + 1)
        count += 1
        
        if count == k:
            break
    
print(que.pop())

Solution (Python):
k = int(input())
ans = [i for i in range(1, 10)]


def generate_lunlun(x):
    y = x % 10
    if 0 <= y-1:
        yield 10*x + y-1
    yield 10*x + y
    if y+1 < 10:
        yield 10*x + y+1


idx = 0
while len(ans) < k:
    x = ans[idx]
    for i in generate_lunlun(x):
        ans.append(i)
    idx += 1

print(ans[k-1])

Solution (Python):
from collections import deque
K=int(input())

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

Solution (Python):
k = int(input())

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


def generate_lunlun(x):
    mod = x % 10

    if mod - 1 >= 0:
        yield x*10 + mod-1

    yield x*10 + mod

    if mod + 1 <= 9:
        yield x*10 + mod + 1


p = 0

while len(lunlun) < k:
    for i in generate_lunlun(lunlun[p]):
        lunlun.append(i)

    p += 1

print(lunlun[k-1])

Solution (Python):
k = int(input())
ans = [i for i in range(1,10)]

i = 0

for i in range(k):
    now = ans[i]
    if str(now)[-1] == '0':
        ans.append(now*10)
        ans.append(now*10+1)
    elif str(now)[-1] == '9':
        ans.append(now*10+8)
        ans.append(now*10+9)
    else:
        ans.append(now*10+now%10-1)
        ans.append(now*10+now%10)
        ans.append(now*10+now%10+1)
    if len(ans) > k:
        break

print(ans[k-1])

Solution (Python):
import queue

K = int(input())

count = 0
q = queue.Queue()
for i in range(1, 10):
    count += 1
    q.put(i)
    if count == K:
        print(i)
        break

result = 0
while count != K:
    tmp = q.get()  
    keta1 = tmp % 10  
    for i in range(-1, 2):
        if keta1 == 0 and i == -1:  
            continue
        if keta1 == 9 and i == 1:  
            continue
        result = tmp * 10 + (keta1 + i)
        q.put(result)  
        count += 1
        if count == K:
            print(result)
            break
        else:
            continue

Solution (Python):
from collections import deque
def solve():
    K = int(input())
    q = deque(list(range(1,10)))
    cnt = 0

    tmp = 0
    while cnt < K:
        tmp = q.popleft()
        cnt += 1

        ones_place = tmp % 10
        if ones_place != 0:
            q.append(tmp*10+ones_place-1)
        q.append(tmp*10+ones_place)
        if ones_place != 9:
            q.append(tmp*10+ones_place+1)
    
    print(tmp)
        
if __name__ == '__main__':
    solve()

Solution (Python):
from collections import deque
k=int(input())
stack = deque([1,2,3,4,5,6,7,8,9])

def lunlun():
    cnt=0
    while True:
        now = stack.popleft()
        cnt += 1
        if cnt == k: return now
        s = str(now)
        for i in range(-1,2):
            temp=int(s[-1]) + i 
            if temp>=0 and temp<10: 
                temp1=int(s + str(temp))
                stack.append(temp1)
print(lunlun())

Solution (Python):
import sys

k = int(sys.stdin.readline().rstrip())

def main(k):
    if k <= 9:
        print(k)
        return
    res = list(range(1, 10))
    k -= 9
    while True:
        nex = []
        for n in res:
            r = n % 10
            n *= 10
            for i in range(-1, 2):
                if 0 <= r + i <= 9:
                    nex.append(n + r + i)
                    k -= 1
                    if not k:
                        print(nex[-1])
                        return
        res = nex.copy()

if __name__ == '__main__':
    main(k)

Solution (Python):
import queue

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

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

Solution (Python):
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])

Solution (Python):
k = int(input())

runrun = [i for i in range(1,10)]

def gen_runrun(x):
    a = x % 10
    if a in [1,2,3,4,5,6,7,8]:
        runrun.append(x * 10 + a - 1)
        runrun.append(x * 10 + a )
        runrun.append(x * 10 + a + 1)
    elif a == 0:
        runrun.append(x * 10 + a )
        runrun.append(x * 10 + a + 1)
    elif a == 9:
        runrun.append(x * 10 + a - 1)
        runrun.append(x * 10 + a )

i = 0
while len(runrun) < k + 10:
    gen_runrun(runrun[i])
    i += 1

print(runrun[k - 1])

Solution (Python):
k = int(input())
lunlun = [1, 2, 3, 4, 5, 6, 7, 8, 9] 

for i in range(k):
    x = lunlun[i]
    if x%10 != 0:
        lunlun.append(x*10+x%10-1)
    lunlun.append(x*10+x%10)
    if x%10 != 9:
        lunlun.append(x*10+x%10+1)
        
print(x)

Solution (Python):
from collections import deque
K = int(input())

que = deque(list(range(1, 10)))

c = 0
while len(que):
    x = que.popleft()
    c += 1
    for m in range(max(0, x % 10 - 1), min(9, x % 10 + 1) + 1):
        que.append(10*x+m)
    
    if c == K:
        print(x)
        break

Solution (Python):
import queue


def strtoNum(l):
    val = ''
    for _ in l:
        val += _
    return int(val)


k = int(input())


if k < 10:
    print(k)
    exit()


lun = queue.Queue()

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


cnt = 9

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

while not lun.empty():
    
    getNum = list(str(lun.get()))
    
    chkNum = int(getNum[len(getNum)-1])
    for i in apdNum[chkNum]:
        cnt += 1
        putNum = getNum + [str(i)]
        if cnt == k:
            print(strtoNum(putNum))
            exit()
        else:
            lun.put(strtoNum(putNum))

Solution (Python):
from collections import deque

k = int(input())
lunlun = []
q = deque([1,2,3,4,5,6,7,8,9])
while len(lunlun) <= k:
    first = q.popleft()
    lunlun.append(first)
    if first%10-1 >= 0:
        q.append(first*10 + (first%10-1))
    q.append(first*10 + first%10)
    if first%10+1 <= 9:
        q.append(10*first + (first%10+1))
print(lunlun[k-1])

Solution (Python):
def dfs(s):
    d=len(s)
    if d>10:
        return
    
    if s!='':
        if s[0]!='0':
            num.add(int(s))

    for c in '0123456789':
        if s=='':
            dfs(s+c)
        else:
            if abs(int(s[-1])-int(c))<=1:
                dfs(s+c)

k=int(input())
num=set()

dfs('')
ans=list(num)
ans.sort()
print(ans[k-1])

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

def main():
    K = int(input())
    q = deque()
    for i in range(1, 10):
        if K == 1:
            print(i)
            exit()
        K -= 1
        q.append(i)
    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()

Solution (Python):
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    K = int(input())
    q = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    heapq.heapify(q)
    while len(q) < K:
        K -= len(q)
        new_q = []
        for i in q:
            d1 = i % 10
            if d1 > 0:
                new_q.append(i * 10 + d1 - 1)
            new_q.append(i * 10 + d1)
            if d1 < 9:
                new_q.append(i * 10 + d1 + 1)
        q = new_q
        heapq.heapify(q)
    print(q[K-1])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from string import digits

k = int(sys.stdin.readline().rstrip())

def main():
    if k <= 9:
        print(k)
        return
    res = list(digits[1:])
    r = k - 9
    nex = []
    while True:
        for n in res:
            o = ord(n[-1])
            for i in range(-1, 2):
                d = chr(o + i)
                if d < '0' or d > '9': continue
                nex.append(n + d)
                r -= 1
                if not r:
                    print(nex[-1])
                    return
        res = nex.copy()
        nex.clear()

if __name__ ==  '__main__':
    main()

Solution (Python):
import sys
from string import digits

k = int(sys.stdin.readline().rstrip())

def main():
    if k <= 9:
        print(k)
        return
    res = list(digits[1:])
    r = k - 9
    while True:
        nex = []
        for n in res:
            o = ord(n[-1])
            for i in range(-1, 2):
                d = chr(o + i)
                if d < '0' or d > '9': continue
                nex.append(n + d)
                r -= 1
                if not r:
                    print(nex[-1])
                    return
        res = nex.copy()    

if __name__ ==  '__main__':
    main()

Solution (Python):
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def main():
    K = int(input())
    q = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    heapq.heapify(q)
    while len(q) < K:
        K -= len(q)
        new_q = []
        for i in q:
            d1 = int(str(i)[-1])
            if d1 > 0:
                new_q.append(i * 10 + d1 - 1)
            new_q.append(i * 10 + d1)
            if d1 < 9:
                new_q.append(i * 10 + d1 + 1)
        q = new_q
        heapq.heapify(q)
    print(q[K-1])

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from string import digits

k = int(sys.stdin.readline().rstrip())

def main():
    r = k
    if r <= 9:
        print(digits[r])
        return
    res = list(digits[1:])
    r -= 9
    while True:
        nex = []
        for n in res:
            o = ord(n[-1])
            for i in range(-1, 2):
                d = chr(o+i)
                if d < '0' or d > '9': continue
                nex.append(n + d)
                r -= 1
                if r == 0:
                    print(nex[-1])
                    return
        res = nex.copy()    

if __name__ ==  '__main__':
    main()

Solution (Python):
K=int(input())
a=set([1,2,3,4,5,6,7,8,9])
prev=set([1,2,3,4,5,6,7,8,9])

while len(a)<K:
  temp=set()
  for now in prev:
    c=now%10
    if c==0:
      temp.add(now*10)
      temp.add(now*10+1)
    elif c==9:
      temp.add(now*10+9)
      temp.add(now*10+8)
    else:
      temp.add(now*10+c-1)
      temp.add(now*10+c)
      temp.add(now*10+c+1)
  prev=temp
  a=a|temp
print(sorted(list(a))[K-1])

Solution (Python):
import sys
from string import digits

k = int(sys.stdin.readline().rstrip())

def main():
    r = k
    if r <= 9:
        print(digits[r])
        return
    res = list(digits[1:])
    r -= 9
    while True:
        nex = []
        for n in res:
            o = ord(n[-1])
            for i in range(-1, 2):
                tail = chr(o+i)
                if tail < '0' or tail > '9': continue
                nex.append(n+tail)
                r -= 1
                if r == 0:
                    print(nex[-1])
                    return
        res = nex.copy()    

if __name__ ==  '__main__':
    main()

Solution (Python):
import sys
import collections

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

k = ni()
runrun = k
ans = 0


class Node(object):
    def __init__(self, nam ):
        self.nam = nam
        if nam == -1:
            ne = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        else:
            nam_digit= nam%10
            nam=nam*10+nam_digit
            ne = [nam - 1, nam, nam + 1]
            if nam_digit == 0:
                ne = [nam, nam+1]
            elif nam_digit == 9:
                ne = [nam-1, nam]
        self.nextlist = ne
        self.nextc = -1
        self.j = False


node = Node(-1)
queue = collections.deque()
j=False
while runrun is not 0:
    queue.extend(node.nextlist)
    nx_nam = queue.popleft()
    node = Node(nx_nam)
    runrun -= 1
ans = node.nam

print("{}".format(ans))

Solution (Python):


import sys
sys.setrecursionlimit(300000)


def solve(K: int):
    def _make(s, idx):
        if idx > 0:
            if s[idx] == '9':
                return None
            prev = int(s[idx - 1])
            cur  = int(s[idx]) + 1
            if abs(prev - cur) > 1:
                return None
        if idx == 0 and s[idx] == '9':
            return '1' + ('0' * len(s))

        ret = s[:idx]
        ret += str(int(s[idx]) + 1)
        for _ in s[idx + 1:]:
            ret += str(max(0, int(ret[-1]) - 1))
        return ret

    def get_next(s):
        idx = 0
        l = len(s)
        for idx in range(l)[::-1]:
            tmp = _make(s, idx)
            if tmp is not None:
                return tmp
        return None

    val = '0'
    for i in range(K):
        val = get_next(val)
    print(val)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    solve(K)

if __name__ == '__main__':
    main()

Solution (Python):
K = int(input())

if K <= 9:
    print (K)
    exit()

lst = [[1] * 11 for _ in range(2)]
lst_append = lst.append
lst[0][10] = 0
lst[1][0] = 0
lst[1][10] = 0

now = 9
p = 0
flag = 0
while True:
    if p == 0:
        lst[flag + 1][0] = lst[flag][0] + lst[flag][1]
        p += 1
        continue
    tmp = lst[flag][p - 1] + lst[flag][p] + lst[flag][p + 1]
    lst[flag + 1][p] = tmp
    if now + tmp >= K:
        break
    now += tmp
    p += 1

    if p == 10:
        p = 0
        flag += 1
        lst_append([0] * 11)








ans = str(p)
flag += 1
while True:
    if flag == 0:
        break
    
    if p >= 1 and K <= now + lst[flag - 1][p - 1]:
        flag -= 1
        ans += str(p - 1)
        p -= 1
    elif K <= now + lst[flag - 1][p - 1] + lst[flag - 1][p]:
        now += lst[flag - 1][p - 1]
        flag -= 1
        ans += str(p)
    else:
        now += lst[flag - 1][p - 1] + lst[flag - 1][p]
        flag -= 1
        ans += str(p + 1)
        p += 1

print (ans)

Solution (Python):
import heapq

K =int(input())

pque = []
for i in range(1, 10):
    heapq.heappush(pque, i)

for i in range(K):
    tmp = heapq.heappop(pque)
    if tmp % 10 == 0:
        heapq.heappush(pque, tmp * 10)
        heapq.heappush(pque, tmp * 10 + 1)
    elif tmp % 10 == 9:
        heapq.heappush(pque, tmp * 10 + 9)
        heapq.heappush(pque, tmp * 10 + 8)
    else:
        next_ = tmp % 10
        heapq.heappush(pque, tmp * 10 + next_ - 1)
        heapq.heappush(pque, tmp * 10 + next_)
        heapq.heappush(pque, tmp * 10 + next_ + 1)

print (tmp)

Solution (Python):
import queue

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

K = int(input())
for _ in range(K):
    now_lunlun_num = q_lunlun_num.get()
    first_digit = now_lunlun_num % 10

    if first_digit != 0:
        q_lunlun_num.put(now_lunlun_num*10 + first_digit - 1)
    
    q_lunlun_num.put(now_lunlun_num*10 + first_digit)

    if first_digit != 9:
        q_lunlun_num.put(now_lunlun_num*10 + first_digit +1 )

print(now_lunlun_num)