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: Runtime Error

Solution code:
x = [1,2,3,4,5,6,7,8,9]
for i in range(1000):
  stri = str(i)
  le = len(stri)
  p = [int(stri[j]) for j in range(le)]
  for k in range(le - 1):
    if abs(p[k] -p[k+1]) <= 1:
      x.extend([i])




n = int(input())
print(x[n])

Submission status: Runtime Error

Solution code:
n=int(input())
now=[1,2,3,4,5,6,7,8,9]
if n<10:
  print(now[n-1])
  exit()
cnt=9
while True:
  next=[]
  for s in now:
    s=str(s)
    if s[-1]!="0":
      cnt+=1
      if cnt<n:
        next.append(s+str(int(s[-1]-1)))
      else:
        print(s+str(int(s[-1]-1)))
        exit()
    cnt+=1
    if cnt<n:
      next.append(s+s[-1])
    else:
      print(s+s[-1])
      exit()
    if s[-1]!="9":
      cnt+=1
      if cnt<n:
        next.append(s+str(int(s[-1]+1)))
      else:
        print(s+str(int(s[-1]+1)))
        exit()
  now=next

Submission status: Runtime Error

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 < 1000:
    num = 1
    count = 0
elif K < 5000:
    num = 110111
    count = 1000
elif K < 10000:
    num = 22111101
    count = 10000


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

print(num-1)

Submission status: Runtime Error

Solution code:
k = int(input())

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

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

        if c + len(b) > k :
            print(b[k-c-len(b)-1])
            break
    
    if c + len(b) > k :
        break
    
    a.append(b)
    c += len(b)

Submission status: Runtime Error

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

def check(n):
    place1 = n % 10
    place10 = n // 10
    if abs place10 - place1 == 1:
        return True
    else:
        return False

while True:
    if check(i):
        lunlun.append(i,i+1,i+2)
        i += 3
        if len(lunlun) > k:
            ans = i
            break
    else:
        i += 8

print(lunlun[k-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math
import numpy as np
# N, K = map(int, input().split(' '))
N = int(input())
run = [list(map(str, range(1, 10)))]
l = 0
count = 9
stop = 10**5
while(1):
    if count > stop:
        break
    nextrun = []
    for i in run[l]:
        if i[-1] == '0':
            nextrun.append(i+'0')
            nextrun.append(i+'1')
        elif i[-1] == '9':
            nextrun.append(i+str(int(i[-1])-1))
            nextrun.append(i+str(int(i[-1])))
        else:
            nextrun.append(i+str(int(i[-1])-1))
            nextrun.append(i+str(int(i[-1])))
            nextrun.append(i+str(int(i[-1])+1))
    run.append(nextrun)
    count += len(nextrun)
    l += 1

newrun = []
for i in run:
    newrun.extend(i)
print(newrun[N-1])

Submission status: Runtime Error

Solution code:
r_l = [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,100,101,110,111]
N = int(input())
print(r_l[N-1])

Submission status: Runtime Error

Solution code:
import math
n,m=map(int,input().split())
a=list(map(int,input().split()))
t=sum(a)
a=list(filter(lambda x: math.ceil(t/(4*m)) < x, a))
print('Yes' if m <= len(a) else 'No')

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr  4 20:58:44 2020

@author: ctiuser
"""

K = int(input())

M = [0,[1,1,1,1,1,1,1,1,1,1]]
s = 9
while K > s:    
    m = [0 for _ in range(10)]
    for i in range(10):
        if i == 0:
            m[i] += M[-1][i] + M[-1][i+1]
        elif i == 9:
            m[i] += M[-1][i-1] + M[-1][i]
        else:
            m[i] += M[-1][i-1] + M[-1][i] + M[-1][i+1]
    M.append(m)
    s += sum(m[1:])
s -= sum(m[1:])
keta = len(M) - 1
ans = ''

i = 0
while K > s:
    i += 1
    s += M[keta][i]

s -= M[keta][i]
ans += str(i)
keta -= 1
d = K - s
#print(ans)
#print(i, d)
while keta > 0:
    if i == 0:
        d -= M[keta][i]
        if d <= 0:
            i = i
            ans += str(i)
            d += M[keta][i]            
        else:
            d -= M[keta][i+1]
            if d <= 0:
                i = i+1
                ans += str(i)
                d += M[keta][i]
    elif i == 9:
        d -= M[keta][i-1]
        if d <= 0:
            i = i-1
            ans += str(i)
            d += M[keta][i]
        else:
            d -= M[keta][i]
            if d <= 0:
                i = i
                ans += str(i)
                d += M[keta][i]
    else:
        d -= M[keta][i-1]
        if d <= 0:
            i = i-1
            ans += str(i)
            d += M[keta][i]
        else:
            d -= M[keta][i]
            if d <= 0:
                i = i
                ans += str(i)
                d += M[keta][i]
            else:
                d -= M[keta][i+1]
                if d <= 0:
                    i = i+1
                    ans += str(i)
                    d += M[keta][i]
        
        
        keta -= 1
#        print(ans)
#        print(i,d)


print(ans)

Submission status: Runtime Error

Solution code:
K = int(input())

def cal():
    count = 9
    d = [[1,2,3,4,5,6,7,8,9]]
    for i in range(10**9):
        d_ = []
        for j in range(len(d[i])):
            a = str(d[i][j])
            if a[-1]=="0":
                for k in [0,1]:
                    d_.append(int(a)*10+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return
            elif a[-1]=="9":
                for k in [8,9]:
                    d_.append(int(a)*10+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return 
            else:
                for k in [-1, 0, 1]:
                    d_.append(int(a)*10+int(a[-1])+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return
            d.append(d_)
if k <= 9:
    print(K)
else:
    cal()

Submission status: Runtime Error

Solution code:
K = int(input())

def cal():
    count = 9
    d = [[1,2,3,4,5,6,7,8,9]]
    for i in range(10**9):
        d_ = []
        for j in range(len(d[i])):
            a = str(d[i][j])
            if a[-1]=="0":
                for k in [0,1]:
                    d_.append(int(a)*10+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return
            elif a[-1]=="9":
                for k in [8,9]:
                    d_.append(int(a)*10+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return 
            else:
                for k in [-1, 0, 1]:
                    d_.append(int(a)*10+int(a[-1])+k)
                    count += 1
                    if K == count:
                        print(d_[-1])
                        return
            d.append(d_)
if k <= 9:
    print(k)
else:
    cal()

Submission status: Runtime Error

Solution code:
K = int(input())

min_r = 0
max_r = 12

def count(idx, n):
    if idx==0:
        return 1
    if n==0:
        return count(idx-1, 1)+count(idx-1, 0)
    elif n==9:
        return count(idx-1, 9)+count(idx-1, 8)
    else:
        return count(idx-1, n-1)+count(idx-1, n)+count(idx-1, n+1)

lists = []
def count_2(idx, n, list_b):
    lis = list_b[:]
    lis.append(str(n))
    if idx==0:
        lists.append(int(''.join(lis)))
        return 1
    if n==0:
        count_2(idx-1, 1, lis)
        count_2(idx-1, 0, lis)
    elif n==9:
        count_2(idx-1, 9, lis)
        count_2(idx-1, 8, lis)
    else:
        count_2(idx-1, n-1, lis)
        count_2(idx-1, n, lis)
        count_2(idx-1, n+1, lis)

d = 0
now = 0
while 1:
    p = sum([count(d, i) for i in range(1, 10)])
    now += p
    if now>K:
        now -= p
        break
    d += 1

sump = 0
for i in range(1, 10):
    sump_old = sump
    sump += count(d, i)
    if sump+now>K:
        break
count_2(d, i, [])
print(lists[K-now-sump_old+1])

Submission status: Runtime Error

Solution code:
K = int(input())
a = []
for i in range(1,1000000):
  s = str(i)
  if(i<10):
    a.append(i)
  elif(i<100):
    if(abs( int(s[0]) - int(s[1]) )<=1):
      a.append(i)
  elif(i<1000):
    if(abs( int(s[0]) - int(s[1]) )<=1 
       and abs( int(s[1]) - int(s[2]) )<=1
      ):
      a.append(i)
  elif(i<10000):
    if(abs( int(s[0]) - int(s[1]) )<=1 
       and abs( int(s[1]) - int(s[2]) )<=1
       and abs( int(s[2]) - int(s[3]) )<=1
      ):
      a.append(i)
  elif(i<100000):
    if(abs( int(s[0]) - int(s[1]) )<=1 
       and abs( int(s[1]) - int(s[2]) )<=1
       and abs( int(s[2]) - int(s[3]) )<=1
       and abs( int(s[3]) - int(s[4]) )<=1
      ):
      a.append(i)
  elif(i<1000000):
    if(abs( int(s[0]) - int(s[1]) )<=1 
       and abs( int(s[1]) - int(s[2]) )<=1
       and abs( int(s[2]) - int(s[3]) )<=1
       and abs( int(s[3]) - int(s[4]) )<=1
       and abs( int(s[4]) - int(s[5]) )<=1
      ):
      a.append(i)
print(a[K-1])

Submission status: Runtime Error

Solution code:
K=int(input())
number_list=[i for i in range(1,10**5 +1)]
cnt=0
for i in number_list:
    if i<=9:
        cnt += 1
        if cnt == K:
            print(i)
            exit()
    else:
        ln=[int(j) for j in str(i)]
        op=[]
        for k in range(len(ln)-1):
            op.appnd(abs(ln[k+1]-ln[k]))
            if sum(op)<=len(ln)-1:
                cnt+=1
                if cnt == K:
                    print(i)
                    exit()

Submission status: Runtime Error

Solution code:
K=int(input())
li=[]
for i in range(1,100001):
  if i < 10**5:
    if i < 10**4:
      if i < 10**3:
        if i < 100:
          if i < 10:
            li.append(i)
          else:#2
            if -1 <= 2*(i//10)-i <= 1:
              li.append(i)
        else:#3
          if -1<=11*(i//100)-(i//10)<=1 and -1<=11*(i//10)-10*(i//100)-i<=1:
            li.append(i)
      else:#4
        if -1<=11*(i//1000)-(i//100)<=1 and -1<=11*(i//100)-10*(i//1000)-i//10<=1 and -1<=11*(i//10)-10*(i//100)-i<=1:
          li.append(i)
    else:#5
      if -1<=11*(i//10000)-(i//1000)<=1 and -1<=11*(i//1000)-10*(i//10000)-i//100<=1 and -1<=11*(i//100)-10*(i//1000)-i//10<=1 and -1<=11*(i//10)-10*(i//100)-i<=1:
        li.append(i)
  else:#6
    li.append(i)
print(li[K-1])

Submission status: Runtime Error

Solution code:
n = int(input())

arr = []
for i in range(10000):
    si = str(i + 1)
    for i2 in range(len(si) - 1):
        if abs(int(si[i2]) - int(si[i2 + 1])) >= 2:
            break
    else:
        arr.append(si)

print(arr[n - 1])

Submission status: Runtime Error

Solution code:
import urllib.request
def D():
    K = int(input())
    data = urllib.request.urlopen('https://oeis.org/A032981/b032981.txt')
    count = 1
    for line in data:
        if count == K:
            print(int(line.split()[1]))
        count += 1
D()

Submission status: Runtime Error

Solution code:
K=int(input())
li=[]
for i in range(1,100001):
  if i < 10**5:
    if i < 10**4:
      if i < 10**3:
        if i < 100:
          if i < 10:
            li.append(i)
          else:#2
            if -1 <= 2*(i//10)-i <= 1:
              li.append(i)
        else:#3
          if -1<=11*(i//100)-(i//10)<=1 and -1<=11*(i//10)-10*(i//100)-i<=1:
            li.append(i)
      else:#4
        if -1<=11*(i//1000)-(i//100)<=1 and -1<=11*(i//100)-10*(i//1000)-i//10<=1 and -1<=11*(i//10)-10*(i//100)-i<=1:
          li.append(i)
    else:#5
      if -1<=11*(i//10000)-(i//1000)<=1 and -1<=11*(i//1000)-10*(i//10000)-i//100<=1 and -1<=11*(i//100)-10*(i//1000)-i//10<=1 and -1<=11*(i//10)-10*(i//100)-i<=1:
        li.append(i)
  else:#6
    li.append(i)
print(li[K])

Submission status: Runtime Error

Solution code:
#dpより愚直に作るか
k = int(input())
lun = [i for i in range(10)]
while len(lun)<k:
    lun2 = []
    for i in lun:
        lun2.append(i*10+(i%10))
        if i%10:
            lun2.append(i*10+(i%10)-1)
        if (i%10)<9:
            lun2.append(i*10+(i%10)+1)
    lun = list(set(lun+lun2))
lun.sort()
print(lun[k])

Submission status: Runtime Error

Solution code:
#dpより愚直に作るか
k = int(input())
lun = [i for i in range(10)]
last = 10
while len(lun)<k:
    lun2 = []
    for i in lun:
        lun2.append(i*10+(i%10))
        if i%10:
            lun2.append(i*10+(i%10)-1)
        if (i%10)<9:
            lun2.append(i*10+(i%10)+1)
    last = len(lun2)
    lun = list(set(lun+lun2))
lun.sort()
print(lun[k])

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split(" "))

c=abs(n-k)
d=abs(c-k)
if(c+d==k):
    if(c>d):
        print(d)
    else:
        print(c)

if(k%n==0):
    if(n>k):
        print(0)
    else:
        print(n) 
    exit()

if(n>k):
    a=n-k*(n//k)
    b=n-k*(n//k+1)
    if(a>b):
        print(b)
    else:
        print(a)

Submission status: Runtime Error

Solution code:
import sys
from math import sqrt
from collections import Counter, defaultdict

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def LIN(n: int):
    return [I() for _ in range(n)]


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    k = I()

    c = 0
    for i in range():
        string = str(i)
        s0 = int(string[0])
        flag = True
        for s in string:
            ints = int(s)
            if abs(ints - s0) > 1:
                flag = False
                break
            s0 = ints
        if flag:
            c += 1
        if c == k:
            print(i)

    pass


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
a = input()


def isLun(n):
    n = [int(i) for i in list(str(n))]
    a = n[0]
    if len(n) > 1:
        for i in n:
            b = abs(a - i)

            if b > 1:
                return False
            a = i
    return True


res = 0
count = 0
i = 0
while count < a:
    i += 1
    if isLun(i):
        count += 1
        res = i
print(res)

Submission status: Runtime Error

Solution code:
import sys
a = input()


def isLun(n):
    n = [int(i) for i in list(str(n))]
    a = n[0]
    if len(n) > 1:
        for i in n:
            b = abs(a - i)

            if b > 1:
                return False
            a = i
    return True


res = 0
count = 0
i = 0
while count < a:
    i += 1
    if isLun(i):
        count += 1
        res = i
        # res.append(str(i + 1))
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np

K = int(input())

top = np.ones(10, dtype=int)
# top[0] = 0
adj = np.eye(10, dtype=int)
adj[1:, :-1] += np.eye(9, dtype=int)
adj[:-1, 1:] += np.eye(9, dtype=int)

counts = [top]
tmp = top
for _ in range(10):
    tmp = tmp.__matmul__(adj)
    counts.append(tmp)

for i in range(10):
    for j in range(1, 10):
        if K > counts[i][j]:
            K -= counts[i][j]
        else:
            break
    else:
        continue
    break

ans = [-1] * (i + 1)
ans[i] = j

for d in range(i, 0, -1):
    for k in range(max(0, j - 1), min(9, j + 1) + 1):
        if K > counts[d - 1][k]:
            K -= counts[d - 1][k]
        else:
            ans[d - 1] = k
            j = k
            break


print("".join(list(map(str, ans))[::-1]))