← 返回题目列表

AtCoder · abc321_c

E. 类似321的搜索器

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

正整数 x 被称为 类似 321 的号码 当满足以下条件时。 这个定义与问题A中的定义相同。

  • 的数字 x 从上到下严格递减。
  • 换句话说,如果 x 有 d 位,每个整数都满足以下条件 i 这样 1 \le i < d:
    • ( i从顶部开始第一个数字 x) > ( (i+1)从顶部开始第一个数字 x).

请注意,所有一位正整数都是类似 321 的数字。

例如, 321, 96410,和 1 是类似 321 的数字,但是 123, 2109,和 86411 不是。

找到 K- 第最小的 321 类数字。

约束

  • 所有输入值均为整数。
  • 1 \le K
  • 至少 K 存在类似 321 的号码。

输入

输入由标准输入按以下格式给出:

K

输出

打印 K- 第最小的 321 类整数。


示例输入 1

15

示例输出 1

32

类似 321 的数字是 (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) 从小到大。
的 树的 15- 其中最小的是 32.


示例输入 2

321

示例输出 2

9610

示例输入 3

777

示例输出 3

983210