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:
k = int(input())
if k <= 12:
    print(k)
    exit()

dp = [[0]*10 for i in range(20)]
for i in range(10):
    dp[0][i] = 1
ans = 9
for i in range(1,18):
    for j in range(1,10):
        if j == 9:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]+dp[i-1][j+1]
    ans += sum(dp[i])
    dp[i][0] = dp[i-1][0] + dp[i-1][1]
    if ans >= k:
        
        s = ""
        for m in range(i,-1,-1):
            if m == i:
                for j in range(9,0,-1):
                    if ans-dp[m][j] >= k:
                        ans -= dp[m][j]
                    else:
                        s += str(j)
                        nex = j
                        
                        break
            else:
                if nex == 9:
                    for j in range(9,7,-1):
                        if ans-dp[m][j] >= k:
                            ans -= dp[m][j]
                        else:
                            s += str(j)
                            nex = j
                            
                            break
                else:
                    for j in range(nex+1,nex-2,-1):
                        if ans-dp[m][j] >= k:
                            ans -= dp[m][j]
                        else:
                            s += str(j)
                            nex = j
                            
                            break



        print(s)
        
        exit()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)


def DFS(num):
    A.add(int(num))
    n=int(num[-1])
    for i in (max(n-1,0),n,min(n+1,9)):
        i=str(i)
        A.add(int(num+i))
        if len(num)<=8:DFS(num+i)


n=int(input())
A=set()
for i in range(1,10):
    DFS(str(i))
A=sorted(A)
print(A[n-1])

Submission status: Accepted

Solution code:
k = int(input())
ans = 1
n = 1
digits = [1]
ind = 1
while ind<k:
    ii = 0
    for i in range(n-1):
        if digits[i]<9 and abs(digits[i]+1-digits[i+1])<=1:
            ii = i
            break
    else:
        if digits[-1]==9:
            digits = [0]*n
            digits.append(1)
            n += 1
            ind += 1
            continue
        if n>1:
            ii = n-1
    digits[ii] += 1
    for j in range(ii-1, -1, -1):
        digits[j] = max(digits[j+1]-1, 0)
    ind += 1

for i in reversed(digits):
    print(i, end='')
print()

Submission status: Accepted

Solution code:
k = int(input())


dnum2list = {}
dnum2list[1] = list(map(str, range(1, 10)))

for i in range(2, 11):
    dnum2list[i] = []
    for num in dnum2list[i - 1]:
        if num[-1] != '0':
            dnum2list[i].append(num + chr(ord(num[-1]) - 1))
        dnum2list[i].append(num + num[-1])
        if num[-1] != '9':
            dnum2list[i].append(num + chr(ord(num[-1]) + 1))

all_vals = []
for vals in dnum2list.values():
    all_vals += [int(v) for v in vals]

all_vals.sort()
print(sorted(all_vals)[k - 1])

Submission status: Accepted

Solution code:
k = int(input())

from collections import deque

count = 0
q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)
q.append(5)
q.append(6)
q.append(7)
q.append(8)
q.append(9)
li = []
while q:
    p = q.popleft()
    li.append(p)
    p = str(p)
    count += 1
    if count==10**5:
        break
    if p[-1]!="9" and p[-1]!="0":
        p = str(p)
        z = p + str(int(p[-1])-1)
        za = p + str(int(p[-1]))
        zb = p + str(int(p[-1])+1)
        q.append(int(z))
        q.append(int(za))
        q.append(int(zb))
    elif p[-1]=="9":
        z = p + str(int(p[-1])-1)
        za = p + str(int(p[-1]))
        q.append(int(z))
        q.append(int(za))
    elif p[-1]=="0":
        z = p + str(int(p[-1])+1)
        za = p + str(int(p[-1]))
        q.append(int(z))
        q.append(int(za))
li.sort()
print(li[k-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def nextrun(x):
    sx = list(str(x))
    for i in reversed(range(len(sx))):
        isInc = True
        if i > 0:
            if int(sx[i]) == 9:
                continue
            if abs(int(sx[i])+1-int(sx[i-1])) <= 1:
                sx[i] = str(int(sx[i])+1)
                for j in range(len(sx)-i-1):
                    sx[i+j+1] = str(max(0,int(sx[i])-j-1))
                return int(''.join(sx))
    if sx[0] == '9':
        ret = ['0']*(len(sx)+1)
        ret[0] = '1'
        return int(''.join(ret))
    else:
        sx[0] = str(int(sx[0])+1)
        for i in range(len(sx)-1):
            sx[i+1] = str(max(0,int(sx[0])-i-1))
        return int(''.join(sx))
        

n = int(input())
a = 0
for i in range(n):
    a = nextrun(a)
print(a)

Submission status: Accepted

Solution code:
K = int(input())

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

len_R_p,len_R_n,digit = 0,9,0
while len_R_n < K:
    for i in range(len_R_p,len_R_n):
        if R[i][digit] == "0":
            R.append(R[i]+"0")
            R.append(R[i]+"1")
        elif R[i][digit] == "9":
            R.append(R[i]+"8")
            R.append(R[i]+"9")
        else:
            R.append(R[i]+str(int(R[i][digit])-1))
            R.append(R[i]+str(int(R[i][digit])))
            R.append(R[i]+str(int(R[i][digit])+1))
    len_R_p = len_R_n
    len_R_n = len(R)
    digit += 1

print(R[K-1])

Submission status: Accepted

Solution code:
k=int(input())
run=[[str(i) for i in range(1,10)],[],[],[],[],[],[],[],[],[]]
#print(run)
i=0
while i<=8:
    for num in run[i]:
        c=int(num[-1])
        if 1<=c<=8:
            run[i+1].append(num+str(c-1))
            run[i+1].append(num+str(c))
            run[i+1].append(num+str(c+1))
        if c==0:
            run[i+1].append(num+"0")
            run[i+1].append(num+"1")
        if c==9:
            run[i+1].append(num+"8")
            run[i+1].append(num+"9")
    #print(len(run[i+1]))
    i=i+1
total=[]
for r in run:
    for s in r:
        total.append(s)
#print(total)
print(total[k-1])
#print(run)

Submission status: Accepted

Solution code:
K = int(input())
start = 1

DP = [[1 for i in range(10)] for j in range(12)]

# 下からの桁数
for j in range(1, 12):
    # その位の数
    for i in range(10):
        DP[j][i] = DP[j-1][i]
        if i != 0:
            DP[j][i] += DP[j-1][i-1]
        if i != 9:
            DP[j][i] += DP[j-1][i+1]
s = 0
# 後ろから考える
res = ""
for j in range(12):
    for i in range(1, 10):
        prev = s
        s += DP[j][i]
        if s >= K:
            res += str(i)
            # print(i, j)
            break
    if s >= K:
        break

top = i
keta = j
sa = K - prev
for k in range(keta-1, -1, -1):
    t = 0
    for j in range(max(0, top-1), min(9, top+1)+1):
        # print("kj", k, j)
        t_prev = t
        t += DP[k][j]
        if t >= sa:
            res += str(j)
            sa -= t_prev
            top = j
            break
print(res)

Submission status: Accepted

Solution code:
k = int(input())
li = [str(i) for i in range(1, 10)]
n = 0
while n < 9:
  rep = li[:]
  for r in rep:
    if r[-1] == "0":
      li.append(r+"0")
      li.append(r+"1")
    elif r[-1] == "9":
      li.append(r+"8")
      li.append(r+"9")
    else:
      x = int(r[-1])
      li.append(r+str(x-1))
      li.append(r+str(x))
      li.append(r+str(x+1))
  n += 1

setli = set(li)
li = list(setli)
#print(li)
intli = [int(i) for i in li]
intli.sort()
#print(intli)
#intli.sort
#print(len(intli))
#print(intli)
print(intli[k-1])

Submission status: Accepted

Solution code:
k=int(input())

def dp(k):
    if k<=9:
        return k
    else:
        prev_keta_nums=[1,2,3,4,5,6,7,8,9]
        count=9
        flag = False
        while True:
            next_keta_nums=[]
            for num in prev_keta_nums:
                num_last = int(str(num)[-1])
                if num_last == 9:
                    cands = [8,9]
                elif num_last == 0:
                    cands = [0,1]
                else:
                    cands = [num_last-1,num_last,num_last+1]
                for cand in cands:
                    new_num=int(str(num)+str(cand))
                    next_keta_nums.append(new_num)
                    count+=1
                    if count == k:
                        flag = True
                    if flag:
                        break
                if flag:
                    break
                else:
                    prev_keta_nums = next_keta_nums
            if flag:
                break
        return next_keta_nums[-1]
print(dp(k))

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    def isr(x):
        a = x % 10
        x //= 10
        b = x % 10
        while x:
            if abs(a - b) > 1:
                return False
            x //= 10
            a, b = b, x % 10
        return True
    dp = [[0] * 11 for _ in range(15)]
    dp2 = [0] * 15
    dp[0][0] = 1
    t = 0

    def nxt(x):
        if x == 0:
            return [0, 1]
        if x == 9:
            return [8, 9]
        return [x - 1, x, x + 1]

    for j in range(1, 10):
        dp[0][j] = 1
        t += dp[0][j]
        if t == K:
            return j

    for i in range(1, 15):
        dp2[i] = t
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
        for j in range(1, 10):
            dp[i][j] = sum(dp[i - 1][j - 1:j + 2])
            if t + dp[i][j] >= K:
                r = j
                K -= t
                for p in reversed(range(i)):
                    t = 0
                    for q in nxt(j):
                        if t + dp[p][q] >= K:
                            K -= t
                            r = r * 10 + q
                            j = q
                            break
                        t += dp[p][q]
                return r
            t += dp[i][j]


print(main())

Submission status: Accepted

Solution code:
K = int(input())
lun = []

def make(n):
    if len(n) > 10:
        return 0
    if int(n) > 3234566667:
        return 0
    else:
        if n[0] == "0":
            p = ["0","1"]
        elif n[0] == "9":
            p = ["8","9"]
        else:
            p = [str(int(n[0])-1),n[0],str(int(n[0])+1)]

        lun.append(int(n))
        for i in p:
            lun.append(int(i+n))
            make(i+n)
        return 0
for i in range(10):
    make(str(i))

ans = list(set(lun))
ans.sort()
#print(ans)
print(ans[K])

Submission status: Accepted

Solution code:
#
from collections import deque


def main():
    k = int(input())
    lun = deque(["1", "2", "3", "4", "5", "6", "7", "8", "9"])
    keta = 0
    while len(lun) <= k:
        keta += 1
        for i in range(1, 10):
            generate_lunlun(lun, "", i, keta)
    print(lun[k - 1])


def generate_lunlun(array, s, c, keta):
    if keta == 0:
        array.append(s + str(c))
        return
    if c > 0:
        generate_lunlun(array, s + str(c), c - 1, keta - 1)
    generate_lunlun(array, s + str(c), c, keta - 1)
    if c < 9:
        generate_lunlun(array, s + str(c), c + 1, keta - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

cnt = 9
lnln = deque(range(1, 10))
lnln = list(map(str, lnln))


def f(n, dq):
    x = int(n[-1])
    if x == 0:
        dq.append(n + str(x))
        dq.append(n + str(x + 1))
        return 2
    elif x == 9:
        dq.append(n + str(x - 1))
        dq.append(n + str(x))
        return 2
    else:
        dq.append(n + str(x - 1))
        dq.append(n + str(x))
        dq.append(n + str(x + 1))
        return 3


for i in lnln:
    if cnt > k:
        break
    cnt += f(i, lnln)


print(lnln[k - 1])
# print(type(lnln[1]))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

K = int(input())
nums = []
def make_num(keta, str_num):
    if len(str_num) == keta:
        nums.append(str_num)
        return
    if str_num[-1] == '0':
        # for i in [0,1,9]:
        for i in [0,1]:
            make_num(keta, str_num + str(i))
    elif str_num[-1] == '9':
        # for i in [0,8,9]:
        for i in [8,9]:
            make_num(keta, str_num + str(i))
    else:
        for i in range(-1, 2):
            make_num(keta, str_num + str(int(str_num[-1])+i))

def enum(keta):
    for i in range(1,10):
        make_num(keta, str(i))

keta = 0
while len(nums) < K:
    keta += 1
    enum(keta)

# print(nums[K-20:])
print(nums[K-1])

Submission status: Accepted

Solution code:
d = {
        0: [0, 1],
        1: [0, 1, 2],
        2: [1, 2, 3],
        3: [2, 3, 4],
        4: [3, 4, 5],
        5: [4, 5, 6],
        6: [5, 6, 7],
        7: [6, 7, 8],
        8: [7, 8, 9],
        9: [8, 9]
    }

def next_list(m):
    tail = int(str(m)[-1])
    return d[tail]

def lunlun(k):
    if k < 10:
        return k

    ans = [-1, [1,2,3,4,5,6,7,8,9]]
    cnt = 9
    for i in range(2,11):
        ans.append([])
        for pre in ans[i-1]:
            for n in next_list(pre):
                next = int( str(pre)+str(n) )
                ans[i].append(next)
                cnt += 1
                if cnt == K:
                    return next

K = int(input())
print(lunlun(K))

Submission status: Accepted

Solution code:
l = [1, 2, 3, 4, 5, 6, 7, 8, 9]
l_temp = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def f(x):
    temp = list(str(x))
    t = int(temp[-1])
    if t == 0:
        return int(str(x) + str(t)), int(str(x) + str(t + 1))
    elif t == 9:
        return int(str(x) + str(t - 1)), int(str(x) + str(t))
    else:
        return int(str(x) + str(t - 1)), int(str(x) + str(t)), int(str(x) + str(t + 1))
       

while len(l) < 10 ** 5:
    temp = []
    for l_t in l_temp:
        tem = list(f(l_t))
        for t in tem:
            temp.append(t)
    for t in temp:
        l.append(t)
    l_temp = temp

K = int(input())
print(l[K-1])

Submission status: Accepted

Solution code:
K = int(input())
ans = [0]
count = 0
def f(n):
    tmp = str(n)
    if int(n) > 3234566667:
        return
    else:
        ans.append(int(n))
    f(str(tmp)+tmp[-1])
    if int(tmp[-1])-1 >= 0:
        f(str(tmp)+str(int(tmp[-1])-1))
    if int(tmp[-1])+1 <= 9:
        f(str(tmp)+str(int(tmp[-1])+1))
f(1)
f(2)
f(3)
f(4)
f(5)
f(6)
f(7)
f(8)
f(9)
ans.sort()
print(ans[K])

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

K = int(input())

cnt = 0
LUN = [[0] * 10 for _ in range(11)]
LUN_AC = [[0] * 10 for _ in range(11)]
LUN[0] = [1] * 10
LUN_AC[1] = [0] + [1] * 9

cnt = 0
for i in range(1, 11):
    # i桁目のLUN数
    for d in range(10):
        c = 0
        c += LUN[i-1][d - 1] if 1 <= d and i > 1 else 0
        c += LUN[i - 1][d]
        c += LUN[i - 1][d + 1] if d < 9 and i > 1 else 0

        if d != 0:
            cnt += c

        LUN[i][d] = c
        LUN_AC[i][d] = cnt

        #print("i,d,cnt", i, d, cnt)

        if K <= cnt:
            break

    if K <= cnt:
        break

#print(i, d)

keta = i
rest = K - cnt + c

ans = []
ans.append(d)

for i in range(keta - 1, 0, -1):
    #print("i,d,rest", i, d, rest)
    c1 = LUN[i][d - 1] if 1 <= d else 0
    if rest <= c1:
        ans.append(d - 1)
        d = d - 1
        continue
    else:
        rest -= c1

    c2 = LUN[i][d]

    if rest <= c2:
        ans.append(d)
        continue
    else:
        rest -= c2

    c3 = LUN[i][d + 1] if d < 9 else 0

    if rest <= c3:
        ans.append(d + 1)
        d = d + 1
        continue
    else:
        rest -= c3

    if rest >= 0:
        print(-1)
        exit()

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

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
ans = [i for i in range(1, 10)]
cal1 = [str(i) for i in range(1, 10)]
cal = deque(cal1)

cnt = 0
while (1):
    tmp = cal.popleft()
    last = tmp[-1]
    flag = False
    if last == '0':
        tmp1 = tmp + '0'
        tmp2 = tmp + '1'
    elif last == '9':
        tmp1 = tmp + '8'
        tmp2 = tmp + '9'
    else:
        flag = True
        down = tmp + str(int(last) - 1)
        middle = tmp + last
        up = tmp + str(int(last) + 1)

    if flag:
        ans.append(int(down))
        ans.append(int(up))
        ans.append(int(middle))
        cal.append(down)
        cal.append(up)
        cal.append(middle)
        cnt += 3
    else:
        ans.append(int(tmp1))
        ans.append(int(tmp2))
        cal.append(tmp1)
        cal.append(tmp2)
        cnt += 2

    if cnt > 10**6:
        break
ans.sort()
# print(ans)
print(ans[k - 1])

Submission status: Accepted

Solution code:
from collections import deque
def lun(i,n,all): #数を返す
    if n >= num: 
        data.append(all)
    else:
        if i != 0: lun(i-1,n+1, all*10+i-1)
        lun(i,n+1,all*10+i)
        if i != 9:lun(i+1,n+1, all*10+i+1)
        

data = deque()
K = int(input())
for num in range(1,11):
    for i in range(1,10):
        lun(i,1,i)

print(data[K-1])

Submission status: Accepted

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

runrun = list(map(str, range(1, 10)))
start = 0
while(True):

    runrun_tmp = copy.deepcopy(runrun[start:])
    start = len(runrun)
    for r in runrun_tmp:
        last_int = int(r[-1])
        tmp = []
        if last_int != 0:
            tmp.append(r+str(last_int-1))
        tmp.append(r+str(last_int))
        if last_int != 9:
            tmp.append(r+str(last_int+1))
        runrun += tmp
    if len(runrun) > K:
        break

print(runrun[K-1])

Submission status: Accepted

Solution code:
def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)

if __name__ == "__main__":
    K = int(input())
    S = [1,2,3,4,5,6,7,8,9]
    for i in range(1,10):
        for k in range(3**i):
            a = base10to(k,3)
            a = "0"*(i-len(a))+a
            for j in range(1,10):
                s = str(j)
                state = 1
                j0 = j
                for l in a:
                    if int(l) == 0:
                        j0 -= 1
                        if j0<0:
                            state = 0
                            break
                        s = s + str(j0)
                    elif int(l) ==1 :
                        s = s+str(j0)
                    else:
                        j0 += 1
                        if j0 ==10:
                            state = 0
                            break
                        s = s + str(j0)
                if state:
                    S.append(int(s))
        S.sort()
    print(S[K-1])

Submission status: Accepted

Solution code:
import sys

K = int(input())


def hoge(Num, X, K):
    if Num == K:
        print(X)
        sys.exit()


if K < 10:
    print(K)
else:
    num1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    num2 = []
    num = 9
    while (True):

        for i in range(len(num1)):  # 桁数
            if num1[i] % 10 != 0:
                num2.append(num1[i] * 10 + ((num1[i] % 10) - 1))
                num += 1
                hoge(num, num1[i] * 10 + ((num1[i] % 10) - 1), K)

            num2.append(num1[i] * 10 + (num1[i] % 10))
            num += 1
            hoge(num, num1[i] * 10 + (num1[i] % 10), K)

            if num1[i] % 10 != 9:
                num2.append(num1[i] * 10 + ((num1[i] % 10) + 1))
                num += 1
                hoge(num, num1[i] * 10 + ((num1[i] % 10) + 1), K)

        num1 = num2[:]
        num2 = []

Submission status: Accepted

Solution code:
K = int(input())
nums = []

def ans(num):
    if num > 3234566667:
        return
    nums.append(num)
    if int(str(num)[-1]) + 1 <= 9:
        tmp = int(str(num) + str(int(str(num)[-1]) + 1))
        ans(tmp)
    if int(str(num)[-1]) - 1 >= 0:
        hoge = int(str(num) + str(int(str(num)[-1]) - 1))
        ans(hoge)
    hage = int(str(num) + str(int(str(num)[-1])))
    ans(hage)

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

nums.sort()
print(nums[K-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def abc161d(k):
    lunArr = [[] for _ in range(10)]
    lunArr[0] = [1, 2, 3, 4, 5, 6, 7, 8, 9,]

    for keta in range(1,10):
        for elem in lunArr[keta-1]:
            base = elem % 10
            if base == 0:
                lunArr[keta].append(elem * 10 + base)
                lunArr[keta].append(elem * 10 + base+1)
            elif base == 9:
                lunArr[keta].append(elem * 10 + base-1)
                lunArr[keta].append(elem * 10 + base)
            else:
                lunArr[keta].append(elem * 10 + base-1)
                lunArr[keta].append(elem * 10 + base)
                lunArr[keta].append(elem * 10 + base+1)

    target = k
    for keta in range(10):
        t_arr = lunArr[keta]
        if target < len(t_arr):
            return t_arr[target-1]
        else:
            target -= len(t_arr)
    else:
        print("k is too large")
        print(target)


###
# main
if(__name__ == '__main__'):
    # input
    k = int(input())
    
    ans = abc161d(k)
    
    # output
    print(ans)
# else:
    # do nothing

Submission status: Accepted

Solution code:
k = int(input())

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

for i in lun_list:
    if str(i)[-1] == '0':
        for j in range(2):
            lun_list.append(int(str(i)+str(j)))
    elif str(i)[-1] == '9':
        for j in range(8,10):
            lun_list.append(int(str(i)+str(j)))
    else:
        for j in range(int(str(i)[-1])-1,int(str(i)[-1])+2):
            lun_list.append(int(str(i)+str(j)))
    if len(lun_list) > k:
        break

print(lun_list[k-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

k = int(input())
ln_list = []
dq = deque([])

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

while len(dq) > 0 and len(ln_list) < k:
    obj = dq.popleft()
#    print(" obj: " + str(obj))
    ln_list.append(obj)
    last_i = int(str(obj)[-1])
#    print("  last_i: " + str(last_i))
    for i in range(-1, 2):
        next_int = last_i + i
        if -1 < next_int < 10:
            tmp = int(str(obj) + str(next_int))
#            print(tmp)
            dq.append(tmp)

print(ln_list[k-1])

Submission status: Accepted

Solution code:
k = int(input())
L = []
ans = 0
for i in range(1, 11):
    L.append([])
if k <= 9:
    print(k)
else:
    for i in range(1,10):
        L[0].append(str(i))
        ans = 9
    for i in range(1,10):
        for j in range(len(L[i-1])):
            if L[i-1][j][i-1] == '9':
                L[i].append(L[i-1][j]+'8')
                L[i].append(L[i-1][j]+'9')
            elif L[i-1][j][i-1] == '0':
                L[i].append(L[i-1][j]+'0')
                L[i].append(L[i-1][j]+'1')
            else:
                L[i].append(L[i-1][j]+str(int(L[i-1][j][i-1])-1))
                L[i].append(L[i-1][j]+str(int(L[i-1][j][i-1])))
                L[i].append(L[i-1][j]+str(int(L[i-1][j][i-1])+1))
    templist = []
    for i in range(10):
        templist = templist + L[i]
    print(templist[k-1])

Submission status: Accepted

Solution code:


def next(ll):
    n = len(ll)
    chk = False

    for i in range(n - 1, -1, -1):

        i_num = int(ll[i])

        if i_num == 9:
            continue

        if i > 0:
            # print (ll)
            if i_num <= int(ll[i - 1]):
                if i == n - 1:
                    return str(int(ll) + 1)
                else:
                    if i_num <= int(ll[i + 1]):
                        chk = True
                        break
                        # return ll[:i] + str(i_num + 1) + ll[i + 1:]
        else:
            if i < n - 1:
                if i_num <= int(ll[i + 1]):
                    chk = True
                        # return str(i_num + 1) + ll[i + 1:]
            else:
                chk = True

    if not chk:
        st = '1' + '0' * n
        return st

    i_num = int(ll[i])
    st = ll[:i]

    # print (i, i_num)

    for j in range(n - i):
        st += str(max(i_num + 1 - j, 0))

    return st

# print (next('1012'))

k = int(input())

num = '1'
c = 1

while c < k:
    c += 1
    num = next(num)

print (num)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush, heappushpop

def next_int(n):
    nums = {0: [0, 1],
            1: [0, 1, 2],
            2: [1, 2, 3],
            3: [2, 3, 4],
            4: [3, 4, 5],
            5: [4, 5, 6],
            6: [5, 6, 7],
            7: [6, 7, 8],
            8: [7, 8, 9],
            9: [8, 9]}
    return nums[n]


K = int(input())
queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]
heapify(queue)
for _ in range(K-1):
    now = heappop(queue)  # 最小値を取り出す
    for next_i in next_int(int(str(now)[-1])):
        heappush(queue, int(str(now)+str(next_i)))

print(heappop(queue))

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
ans = deque([str(i) for i in range(1, 10)])
que = deque(ans)
while que:
    num = que.popleft()
    if num[-1] == '0':
        que.append(num + '0')
        que.append(num + '1')
        ans.append(num + '0')
        ans.append(num + '1')
    elif num[-1] in [str(i) for i in range(1, 9)]:
        n_last = int(num[-1])
        que.append(num + str(n_last-1))
        que.append(num + str(n_last))
        que.append(num + str(n_last + 1))
        ans.append(num + str(n_last - 1))
        ans.append(num + str(n_last))
        ans.append(num + str(n_last + 1))
    else:
        que.append(num + '8')
        que.append(num + '9')
        ans.append(num + '8')
        ans.append(num + '9')
    if len(ans) >= k:
        print(ans[k-1])
        exit()

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def PL(L) : print(*L, sep="\n")

K = I()

stack = [[1],[2],[3],[4],[5],[6],[7],[8],[9]]
ok = [[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]]

i = 0
while len(stack) < K:
    p = stack[i]
    tm = ok[p[-1]]
    
    for t in tm:
        stack.append(p+[t])
    
    i += 1

# print(stack)

for i in stack[K-1]:
    print(i, end="")
print()

Submission status: Accepted

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

k = int(input())

a = []

for i in range(10):
    a.append(str(i))

for i in range(9):
    b = []
    for e in a:
        if e[0] == "0":
            b.append("0"+e)
            b.append("1"+e)
        elif e[0] == "9":
            b.append("8"+e)
            b.append("9"+e)
        else:
            b.append(str(int(e[0])-1)+e)
            b.append(e[0]+e)
            b.append(str(int(e[0])+1)+e)
    for e in b:
        a.append(e)

res = []
for e in a:
    if e[0] != "0":
        res.append(int(e))
res = list(set(res))
res.sort()

print(res[k-1])

Submission status: Accepted

Solution code:
k = int(input())
l = set()


def construct(lunnum: str, depth: int, flag: bool):
    global l
    if depth == 0:
        l.add(int(lunnum))
        return
    m = int(lunnum[-1])
    if (flag):
        for i in range(0, 10):
            construct(lunnum+str(i), depth-1, i == 0)
    elif (m == 0):
        for i in sorted([m, (m + 1) % 10]):
            construct(lunnum + str(i), depth - 1, False)
    elif (m == 9):
        for i in sorted([(m - 1) % 10, m]):
            construct(lunnum + str(i), depth - 1, False)
    else:
        for i in sorted([(m - 1) % 10, m, (m + 1) % 10]):
            construct(lunnum + str(i), depth - 1, False)


construct("0", 10, True)
ls = list(l)
ls.sort()
print(ls[k])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
dxdy=((1,0),(0,1))
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

def resolve():
    k,=pin()
    if k<10:
        print(k)
        return
    else:
        from collections import deque as D
        que=D((i,i) for i in range(1,10))
        num=10
        while(1):
            x,y=que.popleft()
            temp=x%10
            subq=[j for j in range(temp-1,temp+2) if j>=0 and j<10]
            #print(subq)
            for q in subq:
                que.append((x*10+q,num))
                if num == k:
                    print(x*10+q)
                    return
                num+=1
    
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じ,るの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """15"""
        output = """23"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """13"""
        output = """21"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """100000"""
        output = """3234566667"""
        self.assertIO(input, output)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import queue

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

k = int(input())
cou = 0
while True:
    cou += 1
    t = q.get()
    if cou == k:
        print(t)
        exit()
    if t % 10 == 0:
        q.put(t*10)
        q.put(t*10 + 1)
    elif t % 10 == 9:
        q.put(t*10 + 8)
        q.put(t*10 + 9)
    else:
        s = t % 10
        q.put(t*10 + s -1)
        q.put(t*10 + s)
        q.put(t*10 + s + 1)