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:
n = int(input())
ans = [[0 for i in range(10)] for i in range(12)]  # ans[桁数][はじめの数字]
anscount = [[0 for i in range(10)] for i in range(12)]
ansnum = []
# print(ans)
count = 9

import bisect

for i in range(10):
    ans[1][i] = 1
    anscount[1][i] = i
# print(anscount)

j = 0

while count < n:
    for i in range(10):
        if i == 0:
            ans[j + 2][i] = ans[j + 1][i] + ans[j + 1][i + 1]
        elif i == 9:
            ans[j + 2][i] = ans[j + 1][i - 1] + ans[j + 1][i]
            count += ans[j + 2][i]
        else:
            ans[j + 2][i] = ans[j + 1][i - 1] + ans[j + 1][i + 1] + ans[j + 1][i]
            count += ans[j + 2][i]
        anscount[j + 2][i] = count
    # print(anscount)
    # print(ans)
    j += 1
# print(anscount)
# print(ans)

keta = j + 1
hajime = bisect.bisect_left(anscount[keta], n)
# print(anscount[keta])
# print(hajime)
# print(ans[keta-1])
num = anscount[keta][hajime - 1]
sa = n - num
# print(keta,hajime,sa)
ansnum.append(hajime)

count = 0

for i in reversed(range(1, keta)):
    if hajime != 0:
        if sa <= ans[i][hajime - 1]:
            hajime -= 1
        elif sa <= ans[i][hajime - 1] + ans[i][hajime]:
            hajime += 0
            sa -= ans[i][hajime - 1]
        else:
            sa -= (ans[i][hajime - 1] + ans[i][hajime])
            hajime += 1
    else:
        if sa <= ans[i][hajime]:
            hajime += 0
        else:
            sa -= ans[i][hajime]
            hajime += 1
    ansnum.append(hajime)
    # print(i, hajime, sa)
    # print(ansnum)

count = 0
sa = 1
for i in reversed(ansnum):
    count += i * sa
    sa *= 10
print(count)
# 3234566667
# 956なら99999

Submission status: Accepted

Solution code:

q=[]
for i in range(1,10):
    q.append(i)
n=int(input())
ans=0
for i in range(n):
    size=len(q)
    a=q[size-(size-i)]
    if a%10!=0:
        q.append(10*a+a%10-1)
    q.append(10*a+a%10)
    if  a%10!=9:
        q.append(10*a+a%10+1)
print(q[n-1])

Submission status: Accepted

Solution code:
if __name__ == '__main__':
	K = int(input())

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

	ans = 0
	count = 9
	check = 0

	if K < 10:
		ans = L[K][0]
		check = 1

	while check == 0:
		newL = [['']] * 10
		for i in range(10):
			newls = []
			if i == 0:
				for s in L[0]:
					newls.append(str(i)+s)
				for s in L[1]:
					newls.append(str(i)+s)
			elif i == 9:
				for s in L[8]:
					newls.append(str(i)+s)
					count += 1
					if count == K:
						ans = newls[-1]
						check = 1
				for s in L[9]:
					newls.append(str(i)+s)
					count += 1
					if count == K:
						ans = newls[-1]
						check = 1
			else:
				for j in range(-1,2):
					for s in L[i+j]:
						newls.append(str(i)+s)
						count += 1
						if count == K:
							ans = newls[-1]
							check = 1

			newL[i] = newls[:]

		L = newL[:]


	print(int(ans))

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())
q = deque(range(1,10))
for i in range(k):
    x = q.popleft()
    if x % 10 != 0:
        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(x)

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

d = deque(range(1, 10))

cnt = 0
lc = 0
while cnt<=max(0, k-9):
	x = d[lc]
	xdr10 = x%10
	if xdr10 != 0:
		d.append(10*x+xdr10-1)
		cnt += 1
	
	d.append(10*x+xdr10)
	cnt += 1
	
	if xdr10 != 9:
		d.append(10*x+xdr10+1)
		cnt += 1
	lc += 1

print(d[k-1])

Submission status: Accepted

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

print(x)

Submission status: Accepted

Solution code:
def digits_to_number(digits):
    res = 0
    for d in reversed(digits):
        res *= 10
        res += d
    return res


def next_lunlun(n):
    digits = []
    x = n
    while x > 0:
        digits.append(x % 10)
        x //= 10
    for i in range(0, len(digits)-1):
        if digits[i] <= digits[i+1] and digits[i] != 9:
            digits[i] += 1
            for j in range(i-1, -1, -1):
                digits[j] = max(digits[j+1] - 1, 0)
            return digits_to_number(digits)
    if digits[-1] == 9:
        digits = [0] * len(digits)
        digits.append(1)
        return digits_to_number(digits)
    digits[-1] += 1
    for j in range(len(digits)-2, -1, -1):
        digits[j] = max(digits[j+1] - 1, 0)
    return digits_to_number(digits)


def kth_lunlun(k):
    lunlun = 1
    for i in range(0, k-1):
        lunlun = next_lunlun(lunlun)
    return lunlun

if __name__ == '__main__':
    k = int(input())
    print(kth_lunlun(k))

Submission status: Accepted

Solution code:
from collections import deque

K = int(input())
que = deque([i for i in range(1, 10)])
lunlun = []

while que:
    num = que.pop()
    lunlun.append(num)
    for i in range(10):
        if abs(int(str(num)[-1]) - i) <= 1:
            cand = int(str(num) + str(i))
            if cand < 10000000000:
                que.append(cand)

lunlun.sort()
print(sorted(lunlun)[K - 1])

Submission status: Accepted

Solution code:
from queue import Queue
k=int(input())
q=Queue()
for i in range(1,10):
    q.put(i)
if k<=9:
    print(k)
    exit()
a=9
while a<k:
    p=q.get()
    flag=0
    if p%10!=0:
        q.put(p*10+p%10-1)
        a+=1
    if a==k:
        print(p*10+p%10-1)
        exit()
    q.put(p*10+p%10)
    a+=1
    if a==k:
        print(p*10+p%10)
        exit()
    if p%10!=9:
        q.put(p*10+p%10+1)
        a+=1
    if a==k:
        print(p*10+p%10+1)
        exit()

Submission status: Accepted

Solution code:
k=int(input())
from collections import deque
q=deque(list(range(1,10)))
for i in range(k):
    p=q.popleft()
    if i==k-1:
        print(p)
        exit()
    a=p%10
    if 0<a<9:
        q.append(p*10+a-1)
        q.append(p*10+a)
        q.append(p*10+a+1)
    elif a==0:
        q.append(p*10)
        q.append(p*10+1)
    else:
        q.append(p*10+a-1)
        q.append(p*10+a)

Submission status: Accepted

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

    input = sys.stdin.readline
    k = int(input())
    q = deque(range(1, 10))

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k=int(input())
l=list(range(1,10))
for i in l:
    for j in range(max(i%10-1,0),min(i%10+2,10)):
        l+=[i*10+j]
    if len(l)>k:
        break
print(l[k-1])

Submission status: Accepted

Solution code:
ONE_KETA = 10

def main():
	K = int(input())

	# 入力値が一桁
	if(K < ONE_KETA):
		print(K)
		return

	# それ以外
	# キューを作る
	queue_list = [i for i in range(1, ONE_KETA)]
	K -= len(queue_list)

	# 2桁目以降
	while(K > 0):
		# キューを取り出す
		val = queue_list.pop(0)

		# 一桁の値を取り出す
		tmp_s_num = val % ONE_KETA

		for i in range(-1, 2):
			# 末尾9、+1の時は飛ばす
			if(tmp_s_num == 9 and i == 1):
				continue
			elif(tmp_s_num == 0 and i == -1):
				continue
			else:
				# 10倍 + 元の値 + (-1,0,+1)
				tmp_val = val * 10 + tmp_s_num + i
				if(K > 0):
					queue_list.append(tmp_val)
					K -= 1

	# 最後の値が答え
	print(queue_list.pop())
	return

if __name__ == "__main__":
	main()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

K = inputI()


l = [[0,0,0,0,0,0,0,0,0,0]]
a = [0]

s = 0
for N in range(1,11):
  if N == 1:
    l.append([1,1,1,1,1,1,1,1,1,1])
  else:
    l.append([
      l[N-1][0]+l[N-1][1],
      l[N-1][0]+l[N-1][1]+l[N-1][2],
      l[N-1][1]+l[N-1][2]+l[N-1][3],
      l[N-1][2]+l[N-1][3]+l[N-1][4],
      l[N-1][3]+l[N-1][4]+l[N-1][5],
      l[N-1][4]+l[N-1][5]+l[N-1][6],
      l[N-1][5]+l[N-1][6]+l[N-1][7],
      l[N-1][6]+l[N-1][7]+l[N-1][8],
      l[N-1][7]+l[N-1][8]+l[N-1][9],
      l[N-1][8]+l[N-1][9]
    ])
  s += sum(l[N][1:])
  a.append(s)
  

N = 1
while K>a[N]:
  N += 1

ans = []

def first_highest(k):
  n = 1
  while k>a[n]:
    n += 1
  k -= a[n-1]
  i = 1
  while k>l[n][i]:
    k -= l[n][i]
    i+=1
  return(n,int(i),k)

N = first_highest(K)[0]
ans.append(first_highest(K)[1])

def later_highest(n,k):
  global ans
  if n > 1:
    i = max(0,ans[-1]-1)
    while k>l[n][i]:
      k -= l[n][i]
      i+=1
    return(n,int(i),k)
  else:
    if ans[-1] == 0:
      return(1,ans[-1]+k-1,0)
    else:
      return(1,ans[-1]+k-2,0)
  
N -= 1
K = first_highest(K)[2]

while N:
  piropiro = later_highest(N,K)
  ans.append(piropiro[1])
  K = piropiro[2]
  N -= 1

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