D - Concat Power of 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

以下の条件を満たす正整数を 良い整数 とします。

  • 条件：一つ以上の 2 の冪（1,2,4,8,16,\dots）を（重複と並び替えを許して）選んで文字列として結合し、それを整数として解釈することで得られる。

良い整数のうち N 番目に小さいものを求めてください。 ただし N 番目に小さい良い整数は 10^9 以下であることが保証されます。

制約

  • N は正整数
  • N 番目に小さい良い整数は 10^9 以下

入力

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

N

出力

答えを出力せよ。

入力例 1

10

出力例 1

21

良い整数を小さい方から列挙すると 1, 2, 4, 8, 11, 12, 14, 16, 18, 21, \dots です。

入力例 2

69

出力例 2

328

入力例 3

1099898

出力例 3

819264512

Score : 400 points

Problem Statement

We call a positive integer a good integer if it satisfies the following condition.

  • Condition: It can be obtained by choosing one or more powers of 2 (1, 2, 4, 8, 16, \dots) (repetition and reordering allowed), concatenating them as strings, and interpreting the result as an integer.

Find the N-th smallest good integer. It is guaranteed that the N-th smallest good integer is at most 10^9.

Constraints

  • N is a positive integer.
  • The N-th smallest good integer is at most 10^9.

Input

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

N

Output

Output the answer.

Sample Input 1

10

Sample Output 1

21

Listing good integers in ascending order gives 1, 2, 4, 8, 11, 12, 14, 16, 18, 21, \dots.

Sample Input 2

69

Sample Output 2

328

Sample Input 3

1099898

Sample Output 3

819264512