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: Time Limit Exceeded

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


k = int(input())
number = 9

ans = 0
for i in range(10,10**7):
    check = 'OK'
    l = len(str(i))
    keta = list(str(i))
    for j in range(l-1):
        if abs(int(keta[j]) - int(keta[j+1])) <= 1:
            pass
        else:
            check = 'NG'
    if check == 'OK':
        number += 1
        if number == k:
            ans = i
            break
if k <= 9:
    print(k)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

K = int(input())
if K < 12:
  print(K)
  sys.exit() 
  
count = 12

def run(list):
  for i in range(len(list)-1):
    if not abs(int(list[i]) - int(list[i+1])) > 1:
      continue
    else:
      return False      
  return True
if K < 50000:
  for nums in range(21, 3234566667):
    tmp = list(str(nums))

    if run(tmp):
      count +=1
    if K == count:
      print(nums)
      sys.exit()
else:
  count = 100000
  for nums in range(21, 3234566668)[::-1]:
    if K == count:
      print(nums)
      sys.exit()
    tmp = list(str(nums))
    if run(tmp):
      count = count - 1
    if K == count:
      print(nums)
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:
K = int(input())

def runrunConfirm(num):
    flag=True
    str_num=str(num)
    strlen=len(str_num)
    if strlen==1:
        return True
    for i in range(strlen-1):
        tmp=int(str_num[i])-int(str_num[i+1])
        if abs(tmp)>1:
            flag=False
            break
        # if i==0:
        #     tmp=int(str_num[i])-int(str_num[i+1])
        #     if abs(tmp)>1:
        #         flag=False
        #         break
        # elif i==len(str_num)-1:
        #     tmp=int(str_num[i-1])-int(str_num[i])
        #     if abs(tmp)>1:
        #         flag=False
        #         break
        # else:
        #     tmp=int(str_num[i])-int(str_num[i+1])
        #     if abs(tmp)>1:
        #         flag=False
        #         break
            # tmp=int(str_num[i-1])-int(str_num[i])
            # if abs(tmp)>1:
            #     flag=False
            #     break
    return flag

number=1
runrunlist=0
while True:
    if runrunConfirm(number):
        runrunlist+=1
    if runrunlist==K:
        print(number)
        exit()
    number+=1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def cal(x):

    keta = len(str(x))
    if keta == 1:
        return True

    A = np.array([])
    for i in range(keta):
        A = np.append(A, int(str(x)[i]))

    X = np.abs(np.diff(A))
    return np.all(X <= 1)

K = int(input().split()[0])
j = 0
X = 1
while 1:
        if cal(X):
            j = j + 1
            if j == K:
                print(X)
                break
            else:
                X = X + 1
                continue
        else:
            X = X + 1

Submission status: Time Limit Exceeded

Solution code:
def checkLunlun(n):
  check = 0
  s=str(n)
  for i in range(len(s)-1):
    # print(i)
    if not abs(int(s[i]) - int(str(s[i+1]))) <= 1:
      check += 1
    if check > 0:
      break
  if check == 0:
    return True
  else:
    return False

K = int(input())
n = 0
count = 0
while not count == K:
  n+=1
  if checkLunlun(n):
    count += 1
print(n)

Submission status: Time Limit Exceeded

Solution code:
def check_lunlun(num):
    num = str(num)
    front_word = int(num[0])

    is_lunlun = True
    for n in num:
        if abs(front_word - int(n)) > 1:
            is_lunlun = False
            break
        front_word = int(n)

    return is_lunlun


k = int(input())
count = 0

num = 1
while count < k:
    if check_lunlun(num):
        count += 1

    if count == k:
        print(num)

    num += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

K = int(input())
if K < 12:
  print(K)
  sys.exit() 
  
count = 12

def run(list):
  for i in range(len(list)-1):
    if not abs(int(list[i]) - int(list[i+1])) > 1:
      continue
    else:
      return False      
  return True
if K < 10000:
  for nums in range(21, 3234566667):
    tmp = list(str(nums))

    if run(tmp):
      count +=1
    if K == count:
      print(nums)
      sys.exit()
else:
  count = 100000
  for nums in range(21, 3234566668)[::-1]:
    if K == count:
      print(nums)
      sys.exit()
    tmp = list(str(nums))
    if run(tmp):
      count = count - 1
    if K == count:
      print(nums)
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:
k = int(input())

count = 1
init_list = [i for i in range(1, 10)]
if k <= 9:
    print(k)
else:
    while True:
        hit_num = init_list[0]
        if count == k:
            print(hit_num)
            break
        else:
            del init_list[0]
            view_num = int(str(hit_num)[-1])
            hit_num_10 = hit_num * 10
            if view_num == 9:
                # init_list.append(hit_num * 10 + 8)
                # init_list.append(hit_num * 10 + 9)
                init_list.extend([hit_num_10 + 8, hit_num_10 + 9])
                # add_num_list = [8,9]
            elif  view_num == 0:
                # init_list.append(hit_num * 10)
                # init_list.append(hit_num * 10 + 1)   
                init_list.extend([hit_num_10 , hit_num_10 + 1])
             
                # add_num_list = [0,1]
            else:    
                # add_num_list = [view_num-1, view_num, view_num+1]
                init_list.extend([hit_num_10 + (view_num-1), hit_num_10 + (view_num), hit_num_10 + (view_num+1)])

                # init_list.append(hit_num * 10 + (view_num-1))                
                # init_list.append(hit_num * 10 + view_num)                
                # init_list.append(hit_num * 10 + (view_num+1))                
            
            # add_num_list_int = [int(str(hit_num) + str(i)) for i in add_num_list]
            # init_list = init_list + add_num_list_int
        count += 1

Submission status: Time Limit Exceeded

Solution code:
k=int(input())
keta=2
unta=[[]]*10
unta[0]=["1","2","3","4","5","6","7","8","9"]
for _ in range(9):
	for i in range(len(unta[keta-2])):
		if unta[keta-2][i][len(unta[keta-2][i])-1]=="0":
			unta[keta-1].append(("").join(unta[keta-2][i])+"0")
			unta[keta-1].append(("").join(unta[keta-2][i])+"1")
		if unta[keta-2][i][len(unta[keta-2][i])-1]=="9":
			unta[keta-1].append(("").join(unta[keta-2][i])+"8")
			unta[keta-1].append(("").join(unta[keta-2][i])+"9")
		else:
			unta[keta-1].append(("").join(unta[keta-2][i])+str(int(unta[keta-2][i][len(unta[keta-2][i])-1])-1))
			unta[keta-1].append(("").join(unta[keta-2][i])+str(int(unta[keta-2][i][len(unta[keta-2][i])-1])))
			unta[keta-1].append(("").join(unta[keta-2][i])+str(int(unta[keta-2][i][len(unta[keta-2][i])-1])+1))
	keta += 1
unchi=[]
for i in range(10):
	unchi+=unta[i]
print(unchi[k-1])

Submission status: Time Limit Exceeded

Solution code:
c=11
i=11
d=0
a = int(input())
if a>11:
    while i<3234566668:
        i+=1
        f=0
        l = [int(x) for x in list(str(i))]
        for j in range(1,len(str(i))):
            if abs(l[j-1]-l[j])>1:
                f=1
            if l[j-1]-l[j]<-1 and d==0:
                i+=8*10**(len(str(i))-j-1)-1
                d=1
                break
        if f==0:
            c+=1
            d=0
        if c==a:
            print(i)
            break
else:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())

def isRunRun(X):
    x = str(X)
    sa = 0
    for i in range(len(x)-1):
        if abs(int(x[i]) - int(x[i+1])) > 1:
            return False
    return True

if K > 23527:
    num = 99999999
    count = 23527
elif K > 10000:
    num = 22111101
    count = 10000
elif K > 5000:
    num = 110111
    count = 1000
else:
    num = 1
    count = 0

while count < K:
    if isRunRun(num):
        count += 1
    num += 1

print(num-1)

Submission status: Time Limit Exceeded

Solution code:
def lun(x):
    l = [int(_) for _ in list(str(x))]
    if len(l) == 1:
        return True
    else:
        for z in range(len(l) - 1):
            if abs(l[z] - l[z + 1]) > 1:
                return False
    return True


k = int(input())
count = 0
i = 1
while count != k:
    if lun(i):
        count += 1
    i += 1

print(i-1)

Submission status: Time Limit Exceeded

Solution code:
url = "https://atcoder.jp/contests/abc161/tasks/abc161_d"

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

    end_r = 3234566667
    count = 0
    start = 0
    flg = False

    if n <= 12:
        print(n)
        exit()
    elif n <= 50000:
        count = n
    elif n > 50000:
        count = 100000 - n
        start = end_r
        flg = True
    while count != 0:
        if flg:
            start -= 1
        else:
            start += 1
        for i in range(len(str(start)) + 1):
            start_li = [int(v) for v in str(start)]
            if i == len(start_li) - 1:
                count -= 1
                break
            elif abs(start_li[i + 1] - start_li[i]) >= 2:
                break


    print(start)







if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

K = int(input())
if K < 12:
  print(K)
  sys.exit() 
  
count = 12

def run(list):
  for i in range(len(list)-1):
    if not abs(int(list[i]) - int(list[i+1])) > 1:
      continue
    else:
      return False      
  return True
if K < 1000:
  for nums in range(21, 3234566667):
    tmp = list(str(nums))

    if run(tmp):
      count +=1
    if K == count:
      print(nums)
      sys.exit()
else:
  count = 100000
  for nums in range(21, 3234566668)[::-1]:
    if K == count:
      print(nums)
      sys.exit()
    tmp = list(str(nums))
    if run(tmp):
      count = count - 1
    if K == count:
      print(nums)
      sys.exit()

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
def lunlunOrNot(x):
    x = str(x)
    l = len(x)
    flag = True
    for i in range(l-1):
        
        if abs(int(x[i]) - int(x[i + 1])) > 1:
            flag = False
            break
        else:
            flag = True
            continue
    
    if flag:
        return True
    else:
        False
    
    
n = 0
count = 0

while count < k:
    n += 1
    if lunlunOrNot(n):
        count += 1
print(n)

Submission status: Time Limit Exceeded

Solution code:
import math

def runrun(x):
    number_list = []
    while True:
        if x<10:
            low_number = x - (x//10)*10
            number_list.append(low_number)
            x = x//10
            break
        low_number = x - (x//10)*10
        number_list.append(low_number)
        x = x//10

    for i in range(len(number_list)-1):
        if abs(number_list[i]-number_list[i+1])>1:
            return False

    return True

first_input = list(map(lambda x:int(x), input().split(" ")))
#second_input = list(map(lambda x:int(x), input().split(" ")))

K = first_input[0]
count = 0
number = 1

while True:
    if runrun(number):
        count = count+1
    if count==K:
        print(number)
        break
    number = number+1

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
n = 0
while k > 0:
    n += 1
    l = [int(x) for x in list(str(n))]
    flag = True
    for i in range(len(l) - 1):
        if abs(l[i] - l[i + 1]) > 1:
            flag = False
            break
    if flag:
        k -= 1
print(n)

Submission status: Time Limit Exceeded

Solution code:
def lunlunChecker(N):
    num = list(map(int,[l for l in str(N)]))
    flag = True
    for n in range(len(num)-1):
        if abs(num[n]-num[n+1]) > 1:
            flag = False
            break
    return flag
    
K = int(input())
cnt = 10
i = 10
lunlun_nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
if cnt > K:
    output = lunlun_nums.index(K) + 1
else :
    while cnt < K:
        i += 1
        if i//10 in lunlun_nums:
            if lunlunChecker(i):
                lunlun_nums.append(i)
                cnt += 1
    output = i
print(output)

Submission status: Time Limit Exceeded

Solution code:
k=int(input())

def judge(s):
    flag = 1
    if len(s)<=1: return 1
    for i in range(len(s)-1):
        s1, s2 = int(s[i]),int(s[i+1])
        if abs(abs(s1)-abs(s2)) <= 1: continue
        else:
            flag = 0 
            break
    return flag


def bfs1(k, cnt=1, now=1):
    while True:
        s=str(now)
        if judge(s) and k==cnt: return now
        elif judge(s):
            cnt+=1
            now+=1
        else: now+=1

def bfs2(k, cnt=100000, now=3234566667):
    while True:
        s=str(now)
        if judge(s) and k==cnt: return now
        elif judge(s):
            cnt-=1
            now-=1
        else: now-=1    

if k<1000: print(bfs1(k,1,1))
else: print(bfs2(k))

Submission status: Time Limit Exceeded

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

k = int(input())
number = 9

ans = 0
for i in range(10,10**6):
    check = 'OK'
    l = len(str(i))
    keta = list(str(i))
    for j in range(l-1):
        if abs(int(keta[j]) - int(keta[j+1])) <= 1:
            pass
        else:
            check = 'NG'
    if check == 'OK':
        number += 1
        if number == k:
            ans = i%MOD
            break
if k <= 9:
    print(k)
else:
    print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-*-

from sys import stdin


def main():
    K = int(stdin.readline())
    if K <= 12:
        print(K)
        return

    cnt = 12
    num = cnt + 1

    while True:
        s = str(num)
        for i in range(len(s) - 1):
            if abs(int(s[i]) - int(s[i + 1])) > 1:
                break
            if (i == len(s) - 2):
                cnt += 1
                if cnt >= K:
                    print(num)
                    return
        num += 1


if __name__ == "__main__":
    main()