D - Palindromic Number Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 350 点

問題文

非負整数 X を 10 進表記(先行ゼロ無し)で表した文字列が回文である時、X を回文数と呼びます。
例えば 363, 12344321, 0 はいずれも回文数です。

小さい方から N 番目の回文数を求めてください。

制約

  • 1 \leq N \leq 10^{18}
  • N は整数

入力

入力は以下の形式で標準入力から与えられる。

N

出力

小さい方から N 番目の回文数を出力せよ。

入力例 1

46

出力例 1

363

小さい方から 46 番目の回文数は 363 です。

入力例 2

1

出力例 2

0

入力例 3

1000000000000000000

出力例 3

90000000000000000000000000000000009

Score : 350 points

Problem Statement

A non-negative integer X is called a palindrome number if its decimal representation (without leading zeros) is a palindrome.
For example, 363, 12344321, and 0 are all palindrome numbers.

Find the N-th smallest palindrome number.

Constraints

  • 1 \leq N \leq 10^{18}
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N

Output

Print the N-th smallest palindrome number.

Sample Input 1

46

Sample Output 1

363

The 46th smallest palindrome number is 363.

Sample Input 2

1

Sample Output 2

0

Sample Input 3

1000000000000000000

Sample Output 3

90000000000000000000000000000000009