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
from collections import deque
from heapq import heappush, heappop, heapify

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

  q = [i for i in range(1, 11)]
  heapify(q)
  used = set()

  while K:
      n = heappop(q)

      if n in used: continue
      used.add(n)
      K -= 1

      if K == 0:
          print(n)
          break

      last = n % 10

      if last == 0: 
          heappush(q, n*10)
          heappush(q, n*10+1)
      elif last == 9:
          heappush(q, n*10+last)
          heappush(q, n*10-1+last)
      else:
          heappush(q, n*10+last)
          heappush(q, n*10+1+last)
          heappush(q, n*10-1+last)
if __name__ == '__main__':
  	main()

Submission status: Accepted

Solution code:
from collections import deque
k = int(input())
lun = deque([i for i in range(1, 10)])
for i in range(1, k+1):
    num = lun.popleft()
    if num % 10 != 0:
        lun.append(num * 10 + ((num % 10) - 1))
    lun.append(num * 10 + (num % 10))
    if num % 10 != 9:
        lun.append(num * 10 + (num % 10) + 1)
print(num)

Submission status: Accepted

Solution code:
import collections

k = int(input())

li = [str(i) for i in range(1,10)]
q = collections.deque(li)
count = 0
n = 10 ** 6

for i in range(1, n):
    a = q.popleft()
    count += 1
    if count == k:
        print(a)
        exit(0)
    num = int(a[-1])
    if num != 0:
        aa = a + str(num-1)
        q.append(aa)
    aa = a + str(num)
    q.append(aa)
    if num != 9:
        aa = a + str(num+1)
        q.append(aa)

Submission status: Accepted

Solution code:
import queue

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

n = 0
while True:
  val = q.get()
  n += 1
  if n == k:
    print(val)
    break

  if val % 10 != 0:
    q.put(10 * val + (val % 10) - 1)
  q.put(10 * val + (val % 10))
  if val % 10 != 9:
    q.put(10 * val + (val % 10) + 1)

Submission status: Accepted

Solution code:
ans = []
def dfs(i, pre, now):
    global ans
    ans.append(now)
    if i > 10:
        return
    dfs(i + 1, pre, now * 10 + pre)
    if pre + 1 < 10:
        dfs(i + 1, pre + 1, now * 10 + pre + 1)
    if pre - 1 > -1:
        dfs(i + 1, pre - 1, now * 10 + pre - 1)

k = int(input())
for i in range(1, 10):
    dfs(1, i, i)
ans.sort()

print(ans[k - 1])

Submission status: Accepted

Solution code:
from collections import deque

k = int(input())

d = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

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

cnt = 9

while cnt <= 10**5:
    a = d.popleft()
    if a%10 != 0:
        num = 10*a + a%10 - 1
        d.append(num)
        cnt += 1
        if cnt == k:
            print(num)
            exit()

    num = 10*a + a%10
    d.append(num)
    cnt += 1
    if cnt == k:
        print(num)
        exit()
    
    if a%10 != 9:
        num = 10*a + a%10 +1
        d.append(num)
        cnt += 1
        if cnt == k:
            print(num)
            exit()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
K = int(input())
all = []
def dfs(number):
    all.append(number)
    if len(str(number)) == 10:
        return
    first_digit = int(str(number)[-1])
    for n_number in range(first_digit-1, first_digit+2):
        if n_number >= 0 and n_number <= 9:
            dfs(number*10+n_number)

for i in range(1, 10):
    dfs(i)
all.sort()
print(all[K-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
K = int(input())
all = []
def dfs(number):
    all.append(number)
    if len(str(number)) == 10:
        return
    for i in range(-1, 2):
        n_number = number % 10 + i
        if n_number >= 0 and n_number <= 9:
            dfs(number*10+n_number)

for i in range(1, 10):
    dfs(i)
all.sort()
print(all[K-1])

Submission status: Accepted

Solution code:
from collections import deque

# input
K = int(input())

# process/output
dq = deque()
cnt = 0

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

if K > 9:
    cnt = 9
    while cnt < K:
        t = dq.popleft()
        t = t*10 + t%10
        if t%10 != 0:
            dq.append(t-1)
            cnt += 1
        dq.append(t)
        cnt += 1
        if t%10 != 9:
            dq.append(t+1)
            cnt += 1

print(dq[K-cnt-1])

Submission status: Accepted

Solution code:
'''987
988
989
998
999
899
elif lunlun[len(lunlun)-1:]=="99":
		num = nextLun(lunlun[:len(lunlun-1])
		return num+
'''
K = int(input())

def nextLun(lunlun):
	notAllowed = [1,2,3,4,5,6,7,8]
	if len(lunlun)==1:
		return str(int(lunlun)+1)
		
	elif int(lunlun[len(lunlun)-2])+1>=int(lunlun[len(lunlun)-1])+1 and len(str(int(lunlun[len(lunlun)-1])+1))==1:
		
		return str(int(lunlun)+1)
	else:
		num = nextLun(lunlun[:len(lunlun)-1])
		if num[len(num)-1]=="0":
			return num+"0"
		else:
			
			return num+str((int(num[len(num)-1])-1))
def getLun(K):
	lunlun = ["1","2","3","4","5","6","7","8","9"]
	while len(lunlun)<K:
		lunlun.append(nextLun(lunlun[len(lunlun)-1]))
	return lunlun[K-1]
print(getLun(K))

Submission status: Accepted

Solution code:
def lunlun(n):
	nums = set([1, 2, 3, 4, 5, 6, 7, 8, 9])
	while len(nums) < n:
		old_nums = list(nums)
		for num in old_nums:
			num = str(num)
			if num[-1] == '0':
				adds = num + '0'
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + '1'
				if int(adds) not in nums:
					nums.add(int(adds))
			elif num[-1] == '9':
				adds = num + '9'
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + '8'
				if int(adds) not in nums:
					nums.add(int(adds))
			else:
				adds = num + str(int(num[-1]) - 1)
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + str(int(num[-1]))
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + str(int(num[-1]) + 1)
				if int(adds) not in nums:
					nums.add(int(adds))
			# if num[0] == '1':
			# 	adds = '1' + num
			# 	if int(adds) not in nums:
			# 		nums.add(int(adds))
			# 	adds = '2' + num
			# 	if int(adds) not in nums:
			# 		nums.add(int(adds))
			# elif num[0] == '9':
			# 	adds = '8' + num
			# 	if int(adds) not in nums:
			# 		nums.add(int(adds))
			# 	adds = '9' + num
			# 	if int(adds) not in nums:
			# 		nums.add(int(adds))
			# else:
			# 	adds = str(int(num[0]) - 1) + num
			# 	if int(adds) not in nums:
			# 		nums.add(int(adds))
			# 	adds = str(int(num[0])) + num
			# 	if int(adds) not in nums:
			# 		nums.add(int(adds))
			# 	adds = str(int(num[0]) + 1) + num
			# 	if int(adds) not in nums:
			# 		nums.add(int(adds))

	nums = list(nums)
	nums = sorted(nums)
	return nums[n - 1]

n = int(input())
print(lunlun(n))

Submission status: Accepted

Solution code:
def lunlun(n):
	nums = set([1, 2, 3, 4, 5, 6, 7, 8, 9])
	while len(nums) < n:
		old_nums = list(nums)
		for num in old_nums:
			num = str(num)
			if num[-1] == '0':
				adds = num + '0'
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + '1'
				if int(adds) not in nums:
					nums.add(int(adds))
			elif num[-1] == '9':
				adds = num + '9'
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + '8'
				if int(adds) not in nums:
					nums.add(int(adds))
			else:
				adds = num + str(int(num[-1]) - 1)
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + str(int(num[-1]))
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = num + str(int(num[-1]) + 1)
				if int(adds) not in nums:
					nums.add(int(adds))
			if num[0] == '1':
				adds = '1' + num
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = '2' + num
				if int(adds) not in nums:
					nums.add(int(adds))
			elif num[0] == '9':
				adds = '8' + num
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = '9' + num
				if int(adds) not in nums:
					nums.add(int(adds))
			else:
				adds = str(int(num[0]) - 1) + num
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = str(int(num[0])) + num
				if int(adds) not in nums:
					nums.add(int(adds))
				adds = str(int(num[0]) + 1) + num
				if int(adds) not in nums:
					nums.add(int(adds))

	nums = list(nums)
	nums = sorted(nums)
	return nums[n - 1]

n = int(input())
print(lunlun(n))

Submission status: Accepted

Solution code:
from collections import deque
def main(k):
    q = deque([])
    for i in range(1, 10):
        q.append(i)
    
    count = 0
    top = -1
    
    while True:
        top = q.popleft()
 
        count += 1
        if count == k:
            return top
 
        if top%10 != 0:
            q.append(top*10 + top%10-1)
        q.append(top*10 + top%10)
        if top%10 != 9:
            q.append(top*10 + top%10 + 1)
 
    return top
k = int(input())
print(main(k))

Submission status: Accepted

Solution code:
import queue

K = int(input())
q = queue.Queue()
for i in range(1,10):
    q.put(i)
for i in range(K-1):
    x = q.get()
    if x%10 != 0: q.put(x*10 + x%10 - 1)
    q.put(x*10 + x%10)
    if x%10 != 9: q.put(x*10 + x%10 + 1)
print(q.get())

Submission status: Accepted

Solution code:
import queue
n = int(input())
q = queue.Queue()
for i in range(9):
    q.put(i+1)
for i in range(n):
  x = q.get()
  mod_x, mul_x = x%10, 10*x
  if mod_x != 0: q.put(mul_x+mod_x-1)
  q.put(mul_x+mod_x)
  if mod_x != 9: q.put(mul_x+mod_x+1)
print(x)

Submission status: Accepted

Solution code:
import queue

k = int(input())

q = queue.Queue()
x = 0

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

for j in range(k):
    x = q.get()
    if x%10!=0:
        q.put((x*10)+(x%10)-1)
    q.put((x*10)+(x%10))
    if x%10!=9:
        q.put((x*10)+(x%10)+1)

print(x)

Submission status: Accepted

Solution code:
k = int(input())
lunlun = [i+1 for i in range(9)]

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
        

p = 0
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())
l=list(range(1,10))
for i in l:
    if len(l)>k:
        break
    for j in range(max(i%10-1,0),min(i%10+2,10)):
        l.append(i*10+j)
print(l[k-1])

Submission status: Accepted

Solution code:
from queue import Queue

k=int(input())

q = Queue()
count = 0

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

for _ in range(k):
    count = q.get()

    if count%10 != 0:
        q.put(10*count + (count%10) - 1)
    
    q.put(10*count + (count%10))

    if count%10 != 9:
        q.put(10*count + (count%10) + 1)

print(count)

Submission status: Accepted

Solution code:
import queue


def D():
    
    k=int(input())
    q = queue.Queue()
    for i in range(1,10): q.put(i)
    
    for i in range(k):
        valu=q.get()
        if i==k-1: print(valu)
        
        if valu%10 != 0: q.put((10*valu)+(valu%10)-1)
        q.put((10*valu)+(valu%10))
        if valu%10 !=9: q.put((10*valu)+(valu%10)+1)
        
        
        
if __name__=='__main__':
    D()

Submission status: Accepted

Solution code:
K = int(input())

queue = list(range(1, 10))

if K < 10:
    print(K)
else:
    i = 0
    while K > len(queue):
        if queue[i] % 10 != 0:
            l = 10 * queue[i] + queue[i] % 10 - 1
            queue.append(l)
        
        l = 10 * queue[i] + queue[i] % 10
        queue.append(l)
        
        if queue[i] % 10 != 9:
            l = 10 * queue[i] + queue[i] % 10 + 1
            queue.append(l)
        
        i += 1

    print(queue[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(1,k):
    l = q.popleft()
    if (len(q) < k):
        m = l % 10
        if (m != 0):
            q.append(l * 10 + m - 1)
        q.append(l * 10 + m)
        if (m != 9):
            q.append(l * 10 + m + 1)

print(q.popleft())

Submission status: Accepted

Solution code:
import queue
K = int(input())
q = queue.Queue()

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

# print(list(q.queue))

for i in range(1, K):
  x = q.get()
  modx10 = x % 10
  if modx10 != 0:
    q.put(10 * x + modx10 - 1)
  q.put(10 * x + modx10)
  if modx10 != 9:
    q.put(10 * x + modx10 + 1)
  
  #print(i, x, list(q.queue)[len(q.queue)-10:])
print(q.get())

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    ans = 0
    counter = 0
    while True:
        ans += 1
        s_ans = str(ans)
        c_flag = True
        l_ans = len(s_ans)
        skip = 0
        for j in range(1, l_ans):
            if abs(int(s_ans[j])-int(s_ans[j-1])) > 1:
                c_flag = False
                skip = 10**(l_ans-j-1)-1
                break
            if j < l_ans-1 and abs(int(s_ans[j])-int(s_ans[j+1])) > 1:
                c_flag = False
                skip = 10**(l_ans-j-2)-1
                break
        if c_flag == True:
            counter += 1
        else:
            ans += skip
        if counter == K:
            break
    
    print(ans)

main()

Submission status: Accepted

Solution code:
def dfs(c,l):
  n=list()
  for i in l:
    for j in range(max(0,i%10-1),min(i%10+2,10)):
      n.append(i*10+j)
      c-=1
      if c==0:
        return i*10+j
  else:
    return dfs(c,n)

K=int(input())
print(K if K<10 else dfs(K-9,[1,2,3,4,5,6,7,8,9]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k=int(input())
ok=3234566667
ng=0
while ok-ng>1:
  mid=(ok+ng)//2
  s=str(mid)
  dp=[[[0]*2 for _ in range(10)] for _ in range(len(s))]
  for i in range(1,int(s[0])):
    dp[0][i][1]+=1
  dp[0][int(s[0])][0]+=1
  for i in range(1,len(s)):
    for j in range(10):
      if j!=0:
        dp[i][j][1]+=dp[i-1][j][1]+1
      else:
        dp[i][j][1]+=dp[i-1][j][1]
      if j>=1:
        dp[i][j-1][1]+=dp[i-1][j][1]
        if int(s[i])==j-1 and int(s[i-1])==j:
          dp[i][j-1][0]+=dp[i-1][j][0]
        if int(s[i])>j-1:
          dp[i][j-1][1]+=dp[i-1][j][0]
      if j<=8:
        dp[i][j+1][1]+=dp[i-1][j][1]
        if int(s[i])==j+1 and int(s[i-1])==j:
          dp[i][j+1][0]+=dp[i-1][j][0]
        if int(s[i])>j+1:
          dp[i][j+1][1]+=dp[i-1][j][0]
      if int(s[i])==j and int(s[i-1])==j:
        dp[i][j][0]+=dp[i-1][j][0]
      if int(s[i])>j:
        dp[i][j][1]+=dp[i-1][j][0]
  cnt=0
  for i in range(10):
    cnt+=sum(dp[len(s)-1][i])
  if cnt>=k:
    ok=mid
  else:
    ng=mid
print(ok)

Submission status: Accepted

Solution code:
import queue

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

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

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

print(q.get())

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

k = int(readline())
runrun = [i + 1 for i in range(9)]
ans = runrun
for n in range(11):
    check = runrun
    runrun = []
    for x in check:
        if x > 3234566667:
            break
        y = x % 10
        if y > 0:
            runrun.append(x * 10 + y - 1)
        runrun.append(x * 10 + y)
        if y < 9:
            runrun.append(x * 10 + y + 1)
    ans += runrun
print(ans[k - 1])

Submission status: Accepted

Solution code:
k=[]
def abc(n,s,i,b):
    if b:
        if b==n:
            k.append(s)
            return
        k.append(s)
        if i==0:
            abc(n,s*10+0,0,b+1)
            abc(n,s*10+1,1,b+1)
        elif i==9:
            abc(n,s*10+9,9,b+1)
            abc(n,s*10+8,8,b+1)
        else:
            abc(n,s*10+(i-1),i-1,b+1)
            abc(n,s*10+i,i,b+1)
            abc(n,s*10+i+1,i+1,b+1)
    else:
        for i in range(1,10):
            abc(n,s*10+i,i,b+1)
abc(10,0,0,0)

k.sort()
n=int(input())
print(k[n-1])

Submission status: Accepted

Solution code:
## キューとスタックhttp://ailaby.com/deque/
## https://qiita.com/drken/items/6a95b57d2e374a3d3292
from collections import deque
def main():
    K = int(input())
    cnt = 0
    mod = 10
    
    q = deque([])
    for i in range(1, 10):
        q.append(i)
    
    while cnt < K:
        x = q.popleft()
        cnt += 1
        if x%mod == 0:
            q.append(10*x + (x%mod))
            q.append(10*x + (x%mod)+1)
        elif x%mod == 9:
            q.append(10*x + (x%mod) -1)
            q.append(10*x + (x%mod))
        else:
            q.append(10*x + (x%mod)-1)
            q.append(10*x + (x%mod))
            q.append(10*x + (x%mod+1))
    print(x)
main()

Submission status: Accepted

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


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

    k = int(input())
    d = deque()

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

    n = 0
    ans = [str(i) for i in range(1, 10)]

    while n < k:
        di = d.popleft()
        end_digit = di[-1]

        for i in range(10):
            if abs(int(end_digit) - i) <= 1:
                new_di = di + str(i)
                ans.append(new_di)
                d.append(new_di)

                n += 1

    print(ans[k - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
K=int(input())
 
q = collections.deque([1,2,3,4,5,6,7,8,9])


for i in range(K-1):
    t = q.popleft() #リスト最左側の数字を取り出す
    if t%10!=0:     #１０の倍数の時はtの数に１０欠けたもの＋１引いたもの（一つ数の位を上げた中で最小のもの）
                    #１引いても位が変わらないもの
        q.append(t*10+t%10-1) #10, 21, 32 , 121 etc...
    q.append(t*10+t%10)  #11, 22, 122 etc...
    if t%10!=9:     #1足しても位が変わらないもの
        q.append(t*10+t%10+1) #12, 23, 123 etc...
        
        
print(q.popleft())  #上のコードでqの前からK-1の数が後ろに変換して付けられていく
                    #一番左のものを取り付ければそれがK番目のものとなる

Submission status: Accepted

Solution code:
from heapq import heapify,heappop,heappush
def next_num(n):
    if n==0:
        return[0,1]
    elif n==9:
        return[8,9]
    else:
        return[n-1,n,n+1]

K=int(input())
queue=[1,2,3,4,5,6,7,8,9]
heapify(queue)

for _ in range(K-1):
    now=heappop(queue)
    #print("now",now)
    for next_i in next_num(now%10):
        heappush(queue,now*10+next_i)
    #print(queue)
print(queue[0])

Submission status: Accepted

Solution code:
K = int(input())
A = [1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(K):
  x = A[i]
  if x % 10 != 0:
    A.append(10 * x + (x % 10) - 1)
  A.append(10 * x + (x % 10))
  if x % 10 != 9:
    A.append(10 * x + (x % 10) + 1)
else:
  print(A[i])

Submission status: Accepted

Solution code:
#キューを使います
from collections import deque

#関数f:入力xの1の位がyだとした時、「xの末尾に(y-1)を付加したもの」を出力
def f(x):
  s=str(x) #文字列にする
  y=int(s[-1]) #末尾を取り出し数字に戻したものをyとする
  return int(s+str(y-1)) #yから1引いて、元の文字列の末尾に追加

#関数g:入力xの1の位がyだとした時、「xの末尾にyを付加したもの」を出力
def g(x):
  s=str(x) #文字列にする
  y=int(s[-1]) #末尾を取り出し数字に戻したものをyとする
  return int(s+str(y)) #yを元の文字列の末尾に追加

#関数h:入力xの1の位がyだとした時、「xの末尾にy+1を付加したもの」を出力
def h(x):
  s=str(x) #文字列にする
  y=int(s[-1]) #末尾を取り出し数字に戻したものをyとする
  return int(s+str(y+1)) #y+1を元の文字列の末尾に追加

#入力受け取り
K=int(input())

#キューの準備
q=deque()

#キューには1から9の整数を先に入れておく
for i in range(1, 10):
  q.append(i)
  
#キューから数字を取り出し、末尾に数字を付けることで作れるルンルン数をキューに追加する
#この操作をK-1回行う
for i in range(K-1):
  num=q.popleft() #キューから数字を取り出す
  if num%10!=0: #末尾が0の時は、末尾から-1した数字を付加してもルンルン数とならないため除外
    q.append(f(num))
    
  q.append(g(num))
  
  if num%10!=9: #末尾が9の時は、末尾に+1した数字を付加してもルンルン数とならないため除外
    q.append(h(num))
    
print(q.popleft()) #K回目に出てくるルンルン数を出力

Submission status: Accepted

Solution code:
# python3
# -*- coding: utf-8 -*-
import sys
import math
from fractions import gcd
from itertools import count, permutations, combinations, combinations_with_replacement, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint

INF = float('inf')

ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
lmtx = lambda h: [list(map(int, lmis())) for _ in range(h)]
sys.setrecursionlimit(1000000000)


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


# main
k = ii()
d = deque()

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

x = 1

for _ in range(k):
    x = int(d.popleft())

    if x % 10 != 0:
        d.append(10 * x + x % 10 - 1)

    d.append(10 * x + x % 10)

    if x % 10 != 9:
        d.append(10 * x + x % 10 + 1)

print(x)

Submission status: Accepted

Solution code:
from collections import deque
from math import log10

K = int(input())

que = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])


for _ in range(K):
    v = que.popleft()
    # print(v)
    d = int(log10(v)+1)
    res = v
    
    l = v % 10

    if l != 0: que.append(v*10 + l-1)
    que.append(v*10 + l)
    if l != 9: que.append(v*10 + l+1)

print(res)

Submission status: Accepted

Solution code:
#abc161 d 
k=int(input())

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

def lunlun_generate(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


p=0
while len(lunlun)<k:
    for new_lunlun in lunlun_generate(lunlun[p]):#３つ目のyieldが判定されるとfor文を抜ける
        lunlun.append(new_lunlun)
    p+=1
    
print(lunlun[k-1])

Submission status: Accepted

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

q = collections.deque([1,2,3,4,5,6,7,8,9])
for i in range(K-1):
    t = q.popleft()
    if t%10!=0:
        q.append(t*10+t%10-1)
    q.append(t*10+t%10)
    if t%10!=9:
        q.append(t*10+t%10+1)
print(q.popleft())

Submission status: Accepted

Solution code:
import queue
k = int(input())
q = queue.Queue()
cnt = 0
for i in range(1,10):
    q.put(i)
while True:
    a = q.get()
    cnt += 1
    if cnt == k:
        print(a)
        break
    else:
        s = a%10
        if s != 0:
            q.put(10*a + s-1)
        q.put(10*a + s)
        if s != 9:
            q.put(10*a + s+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()
    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:
import queue

K = int(input())

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

for i in range(K):
    ans = num_queue.get()
    if ans % 10 != 0:
        num_queue.put(10 * ans + ans % 10 - 1)
    num_queue.put(10 * ans + ans % 10)
    if ans % 10 != 9:
        num_queue.put(10 * ans + ans % 10 + 1)
        
print(ans)

Submission status: Accepted

Solution code:
lunnum = [None for i in range(100)]
lunnum[1] = (1, 2, 3, 4, 5, 6, 7, 8, 9)

def gen_keta(x):
    for y in lunnum[x-1]:
        r = y % 10
        if r > 0:
            yield 10*y + (r-1)
        yield 10*y + r
        if r < 9:
            yield 10*y + (r+1)

for i in range(2,11):
    lunnum[i] = tuple(gen_keta(i))

def ans(x):
    n = 1
    while True:
        if x <= len(lunnum[n]):
            return lunnum[n][x-1]
        x -= len(lunnum[n])
        n += 1

k = int(input())
print(ans(k))

Submission status: Accepted

Solution code:
def f(N): # N is string
    k = len(N)
    dp = [[[[0 for _ in range(10)] for _ in range(2)] for _ in range(2)] for _ in range(k+1)]
    for j in range(10):
        dp[1][0][0][j]=(j==int(N[0]))
        dp[1][0][1][j]=0
        dp[1][1][0][j]=(j<int(N[0]))
        dp[1][1][1][j]=0
    for i in range(2,k+1):
        for j in range(10):
            for m in range(10):
                dp[i][0][1][j] += (dp[i-1][0][0][m]+dp[i-1][0][1][m])*(abs(m-j)<=1)*(j==int(N[i-1]))
            dp[i][1][0][j]=1
            for m in range(10):
                dp[i][1][1][j] += (dp[i-1][0][0][m]+dp[i-1][0][1][m])*(abs(m-j)<=1)*(j<int(N[i-1]))\
                                    +dp[i-1][1][1][m]*(abs(m-j)<=1)
            for m in range(1,10):
                dp[i][1][1][j] += dp[i-1][1][0][m]*(abs(m-j)<=1)
    cnt = 0
    for j in range(10):
        cnt += dp[k][0][0][j]+dp[k][0][1][j]+dp[k][1][0][j]+dp[k][1][1][j]
    return cnt-1
K = int(input())
low = 0
high = 4*10**9
while high-low>1:
    mid = (high+low)//2
    n = f(str(mid))
    if n<K:
        low = mid
    elif n>=K:
        high = mid
print(high)

Submission status: Accepted

Solution code:
from collections import deque

max_int=int(input().rstrip())

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

for i in range(max_int):
    int_i = q.popleft()
    i_mod10 = int_i%10 #末尾の数字

    if i_mod10==0:
        q.append(10*int_i+i_mod10)
        q.append(10*int_i+i_mod10+1)
    elif i_mod10==9:
        q.append(10*int_i+i_mod10-1)
        q.append(10*int_i+i_mod10)
    else:
        q.append(10*int_i+i_mod10-1)
        q.append(10*int_i+i_mod10)
        q.append(10*int_i+i_mod10+1)
print(int_i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import copy
from collections import deque

def main():

    k=int(input())
    l = list(map(str, range(1, 10)))
    
    for i in range(k):
        t = l[i][-1]
        
        if t =='0':
            l.append(l[i] + '0')
            l.append(l[i] + '1')
            

        elif t =='9':
            l.append(l[i]+'8')
            l.append(l[i]+'9')

        else:
            for j in range(-1, 2):
                l.append(l[i]+str(int(t)+j))
    
    print(sorted(map(int,l))[k-1])

main()

Submission status: Accepted

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

print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#D

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

  import copy

  ss = ["1","2","3","4","5","6","7","8","9"]
  ss2 = []
  ss3 = ss

  nx = {"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"],
  }

  i=0
  while i<K:
    for s in ss:
      nxi = nx[s[-1]]
      ss2 += [s+n for n in nxi]
      i+=len(nxi)
    ss = copy.deepcopy(ss2)
    ss3 += ss
    ss2 = []

  print(int(ss3[K-1]))
main()

Submission status: Accepted

Solution code:
k = int(input())
ans = [1,2,3,4,5,6,7,8,9]
now = 0
for i in ans:
  if now == 100000:
    break
  x = int(str(i)[-1])
  for j in range(max(0,x-1),min(x+2,10)):
    mini_ans = i * 10 + j
    ans.append(mini_ans)
    now += 1
print(ans[k-1])

Submission status: Accepted

Solution code:
k=int(input())
l=list(map(str,range(1,10)))
for i in range(k):
    x=l[i][-1]
    if x=='0':
        l.append(l[i]+x)
        l.append(l[i]+'1')
    elif x=='9':
        l.append(l[i]+'8')
        l.append(l[i]+x)
    else:
        n=int(x)
        l.append(l[i]+str(n-1))
        l.append(l[i]+x)
        l.append(l[i]+str(n+1))
print(sorted(map(int,l))[k-1])

Submission status: Accepted

Solution code:
import queue

#input
K = int(input())

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

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

Submission status: Accepted

Solution code:
a = int(input())

b = [[i-1,i,i+1]for i in range(0,10)]
b = [[j for j in i if j >= 0 and j < 10]for i in b]

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

for i in c:
  istr = str(i)
  for k in b[int(istr[-1])]:
    n = i*10 + k
    c.append(n)
  if len(c) >= a:
    break

print(c[a-1])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


k = I()
dq = deque([i for i in range(1, 10)])
for i in range(k):
    x = dq.popleft()
    k = x % 10
    if k:
        dq += [x * 10 + k - 1]
    dq += [x * 10 + k]
    if k != 9:
        dq += [x * 10 + k + 1]


print(x)

Submission status: Accepted

Solution code:
if True:
    n = int(input())
else:
    n = 100000;
    # n=15
# print(n)

count =0
list_old = [1,2,3,4,5,6,7,8,9]
count = len(list_old)
if count >= n:
    print(list_old[n-1])
    exit()

while(count < n):
    list_new = []
    keta = len(str(list_old[0]))
    # print("keta")
    # print(keta)
    for num in list_old:
        str_num = str(num)
        last_num = int(str_num[len(str_num) - 1]);
        # print("==========")
        # print(str_num)
        # print(last_num)
        if last_num == 0:
            list_new.append(num*10 + last_num)
            list_new.append(num*10 + 1)
        elif last_num == 9:
            list_new.append(num*10 + 8)
            list_new.append(num*10 + last_num)
        else:
            list_new.append(num*10 + last_num-1)
            list_new.append(num*10 + last_num)
            list_new.append(num*10 + last_num+1)
    # print(count)
    # print(list_new)
    if count + len(list_new) < n:
        list_old = list_new
        count += len(list_old)
    else:
        print(list_new[n-count-1])
        break
        # list_old = list_new
        # count += len(list_old)

# print("====")
# print(list_new)
# print(list_old)
# print(count)
# print(count-1-n)
# print(list_old[count-1-n]);