Pythonで競プロしてる 
小さい方からK番目のルンルン数を求める問題です。
（ルンルン数とは、十進数表記した際に、隣り合うどの2つの桁の値についても、差の絶対値が1以下のものだそうです）
提出
import collections
k = int(input())
li = [str(i) for i in range(1,10)]
st_li = li[:]
q = collections.deque(li)
count = 0
n = 10 ** 10
for i in range(1, n):
a = q.popleft()
num = int(a[-1])
if num != 0:
aa = a + str(num-1)
st_li.append(aa)
q.append(aa)
count += 1
aa = a + str(num)
st_li.append(aa)
q.append(aa)
count += 1
if num != 9:
aa = a + str(num+1)
st_li.append(aa)
q.append(aa)
count += 1
if count > k:
print(st_li[k-1])
exit(0)この問題は、collectionsモジュールの「deque」を使用します。
これを使うことで、先頭の要素を取得・削除する際に、時間コストを少なくすることができます。
最初に文字列のリスト
li = [str(i) for i in range(1,10)]
# li = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]を作っておいて、先頭の文字列を取得・削除（popleft()を使用）します。
そして、取得した文字列の語尾の数字と誤差が1以内の数字を後ろにつけて、リストに加える、という操作を順番にやっていき、k番目にきたものが答えになります。
最初はqから「1」を取得し、後ろに「0」「1」「2」を足して、それぞれ「10」「11」「12」にしてから、qの最後に加えます。
他にも例えば、qの先頭に「21」があり、それを取得したときには、「210」「211」「212」をqの最後に加えることになります。
「st_li」には、ルンルン数が1から順番に入っている状態です。
「count」がkより大きくになったときに「st_li[k-1]」に入っているものが答えになります。
上記では文字列のリストを作って操作していますが、工夫すれば数字のリストでも同じことが可能です。
