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:
import sys
input = sys.stdin.readline
import itertools

lunlun = [[] for i in range(11)]

def main():
    n = int(input())
    for i in range(100):
        flag = True
        l = len(str(i))
        if l == 1:
            lunlun[l - 1].append(i)
        else:
            for a in range(1, len(str(i))):
                if abs(int(str(i)[a - 1]) - int(str(i)[a])) >= 2:
                    flag = False
                    break
            if flag:
                lunlun[l - 1].append(i)
            else:
                continue
    for j in range(1, 9):
        for a in lunlun[j]:
            for b in range(10):
                if abs(int(str(a)[-1]) - b) < 2:
                    lunlun[j+1].append(int(str(a)+str(b)))
    lunlun2 = list(itertools.chain.from_iterable(lunlun))
    print(lunlun2[n])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

dq = deque(range(1, 10))
cnt = 9
li = []
while cnt < 10 ** 5 + 10:
    num = dq.popleft()
    li.append(num)
    lst = num % 10
    if lst == 0:
        dq.append(num * 10)
        dq.append(num * 10 + 1)

    elif lst == 9:
        dq.append(num * 10 + 8)
        dq.append(num * 10 + 9)

    else:
        for i in range(lst - 1, lst + 2):
            dq.append(num * 10 + i)

    cnt += 1

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

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)  # import sysすること！再帰の深さ制限を緩くする
n = int(input())
count = 0
ans = []
if n <= 9:
    print(n)
    exit()


def dfs(pre_str, keta):
    global count, ans
    # print(pre_str)
    if len(pre_str) == keta:
        count += 1
        ans = pre_str
        if count+9 == n:
            print(ans)
            exit()
        return

    start = int(pre_str[-1])-1
    for i in range(start, start+3):
        if 0 <= i <= 9:
            dfs(pre_str+str(i), keta)
    return


for i in range(2, 100):
    for j in range(1, 10):
        dfs(str(j), i)

Submission status: Accepted

Solution code:
def lunlundfs(num, digs):
    if digs == 0:
        return [num]
    if num > 0:
        a = lunlundfs(num-1, digs-1)
    else:
        a = []
    b = lunlundfs(num, digs-1)
    if num < 9:
        c = lunlundfs(num+1, digs-1)
    else:
        c = []
    res = []
    for x in a:
        res.append(num*10**digs + x)
    for x in b:
        res.append(num*10**digs + x)
    for x in c:
        res.append(num*10**digs + x)
    return res

def genlunlun(dig):
    lunlunlist = []
    for front in xrange(1,10):
        for d in xrange(dig):
            lunlunlist.extend(lunlundfs(front,d))
    lunlunlist = sorted(lunlunlist)
    return lunlunlist

ll = genlunlun(10)
k = int(raw_input())
print ll[k-1]

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque
k = int(input())
for digit in range(1,11):#最大で10桁まである
    q = []
    cnt = 0
    for i in range(10):#1の位は0~9
        s = str(i)
        if digit == 1:
            if s[0] != "0":
                cnt += 1
                if cnt == k:
                    print(s)
                    exit()
            continue
        plus = 1
        stack = deque(s)
        while len(stack[0]) < digit:
            t = stack.popleft()
            top = int(t[0])
            for j in [top-1,top,top+1]:
                if j >= 0 and j <= 9:
                    l = str(j) + t
                    stack.append(l)
        while stack:
            t = stack.popleft()
            if t[0] != "0":
                cnt += 1
                q.append(t)
    q.sort()
    #print(q,cnt)
    if k > cnt:
        k -= cnt
    else:
        print(q[k-1])
        exit()

Submission status: Accepted

Solution code:
K = int(input())
A = [1,2,3,4,5,6,7,8,9]
for i in range(len(A)):
    if A[i] != 9:
        for j in range(-1,2):
            a = int(str(A[i]) + str(A[i]+j))
            A.append(a)
    else:
        A.append(98)
        A.append(99)
A.append(100)
A.append(101)
L1 = len(A.copy())
for i in range(10,L1):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L2 = len(A.copy())
for i in range(L1,L2):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B%10) + j))
            A.append(a)
L3 = len(A.copy())
for i in range(L2,L3):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L4 = len(A.copy())
for i in range(L3,L4):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L5 = len(A.copy())
for i in range(L4,L5):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L6 = len(A.copy())
for i in range(L5,L6):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L7 = len(A.copy())
for i in range(L6,L7):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
L8 = len(A.copy())
for i in range(L7,L8):
    B = A[i]
    if B % 10 == 0:
        A.append(int(str(B) + '0'))
        A.append(int(str(B) + '1'))
    elif B % 10 == 9:
        A.append(int(str(B) + '8'))
        A.append(int(str(B) + '9'))
    else:
        for j in range(-1, 2):
            a = int(str(B) + str((B % 10) + j))
            A.append(a)
A = sorted(A)
# print(A)
print(A[K-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
def solve(K):
    d = defaultdict(list)

    d[0] = ["00", "01", "10", "11", "12"]
    d[1] = ["00", "01", "10", "11", "12", "21", "22", "23"]
    d[2] = ["10", "11", "12", "21", "22", "23", "32", "33", "34"]
    d[3] = ["21", "22", "23", "32", "33", "34", "43", "44", "45"]
    d[4] = ["32", "33", "34", "43", "44", "45", "54", "55", "56"]
    d[5] = ["43", "44", "45", "54", "55", "56", "65", "66", "67"]
    d[6] = ["54", "55", "56", "65", "66", "67", "76", "77", "78"]
    d[7] = ["65", "66", "67", "76", "77", "78", "87", "88", "89"]
    d[8] = ["76", "77", "78", "87", "88", "89", "98", "99"]
    d[9] = ["87", "88", "89", "98", "99"]

    initial = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23, 32, 33,
               34, 43, 44, 45, 54, 55, 56, 65, 66, 67, 76, 77, 78, 87, 88, 89, 98, 99]
    if K < len(initial):
        print(initial[K])
        return

    counter = len(initial)
    while True:
        new_adj = defaultdict(list)
        for i in range(0, 10):
            for j in d[i]:  # 最初の文字がiのとき
                n = (str(i)+j)
                if(n[0]!="0"):
                    counter += 1
                if counter == K+1:
                    print(n)
                    return

                new_adj[i].append(n)
                if i != 0:
                    new_adj[i-1].append(n)
                if i != 9:
                    new_adj[i+1].append(n)

        d = new_adj
K = int(input())
solve(K)
#solve(100000)
#print(3234566667)

Submission status: Accepted

Solution code:
K=int(input())
Xs=[1,2,3,4,5,6,7,8,9]
s=0
e=9
while K > len(Xs):
    for i in range(e-s):
        n=list(str(Xs[s+i]))
        if int(n[-1])-1 >= 0:
            Xs.append(int(''.join(n+[str(int(n[-1])-1)])))
        Xs.append(int(''.join(n+[str(int(n[-1]))])))
        if int(n[-1])+1 <= 9:
            Xs.append(int(''.join(n+[str(int(n[-1])+1)])))
    s=e
    e=len(Xs)
print(Xs[K-1])

Submission status: Accepted

Solution code:
K = int(input())

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

lst = [[1] * 11 for _ in range(2)]

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)

# print ('now', now)
# print ('p', p)
# print ('flag', flag)
# print (lst[0])
# print (lst[1])

#先頭がpでかつ現在地がnow
ans = str(p)
flag += 1
while True:
    if flag == 0:
        break
    # print (p)
    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)

# for tmp in lst:
#     print (tmp)