← 返回题目列表

AtCoder · abc443_f

F. 不增加的数字

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

分数: 525 点

问题陈述

正整数 X 被称为 好整数 当且仅当满足以下条件:

  • 当 X 用十进制书写,个位,十位, \ldots 形成一个非递增序列。
    • 更正式地说,唯一的非负整数序列 (d_0,d_1,\ldots) 满意 \displaystyle X=\sum_{i=0}^{\infty} d_i10^i (0\le d_i < 10) 形成一个非递增序列。

例如, 112389, 1,和 777 是很好的整数,但是 443 和 404 不是好的整数。

给你一个正整数 N.

判断是否存在一个好的整数,它是 N,如果存在,求其最小值。

约束

  • 1\le N\le 3\times 10^6
  • 所有输入值均为整数。

输入

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

N

输出

如果不存在一个好的整数,它是 N,输出 -1.

如果存在,输出一个好整数的最小值,该整数是 N.


示例输入 1

21

示例输出 1

126

126 是的倍数 21,我们有 6 \geq 2 \geq 1 \geq 0 \geq \ldots,所以它是一个很好的整数。不存在小于的好整数 126 这是的倍数 21,所以输出 126.


示例输入 2

10

示例输出 2

-1

示例输入 3

3

示例输出 3

3

示例输入 4

1089

示例输出 4

9999999999999999999999

答案可能是 2^{64} 或更大。