100 atcoder#ABC161D. [ABC161D] Lunlun Number

[ABC161D] Lunlun Number

Score : 400400 points

Problem Statement

A positive integer XX is said to be a lunlun number if and only if the following condition is satisfied:

  • In the base ten representation of XX (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 11.

For example, 12341234, 11, and 334334 are lunlun numbers, while none of 3141531415, 119119, or 1357913579 is.

You are given a positive integer KK. Find the KK-th smallest lunlun number.

Constraints

  • 1K1051 \leq K \leq 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

KK

Output

Print the answer.

15
23

We will list the 1515 smallest lunlun numbers in ascending order: 11, 22, 33, 44, 55, 66, 77, 88, 99, 1010, 1111, 1212, 2121, 2222, 2323. Thus, the answer is 2323.

1
1
13
21
100000
3234566667

Note that the answer may not fit into the 3232-bit signed integer type.