← 返回题目列表

AtCoder · icpc2015autumn_b

B. 更改密码

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

问题陈述

许多设施都使用密码身份验证。 JAG的办公室也使用密码认证。进入他们的办公室需要密码。密码是一串 $N$ 数字'0'-'9'。该密码会定期更改。 JAG 安全部门的一名工作人员 Taro 决定使用以下规则从旧密码生成新密码。

  1. 新密码由与原始密码相同的 $N$ 位数组成,并且每个数字在新密码中最多出现一次。它可以有一个前导零。 (请注意,旧密码可能包含两次或更多次相同的数字。)
  2. 新密码在上述限制范围内最大化了与旧密码的差异。 (两个密码之间差异的定义如下所述。)
  3. 如果有两个或多个候选者,则选择读取为整数时具有最小值的那个。

两个密码之间的差异由 $min(|a-b|, 10^N-|a-b|)$ 定义,其中 $a$ 和 $b$ 是两个密码表示的整数。 例如,“11“和”42“是31,和”之间的区别987“和”012”是 25。

太郎想用计算机正确计算出新密码,但他不擅长编程。因此,他要求你写一个程序。您的任务是编写一个程序,从旧密码生成新密码。


输入

输入由单个测试用例组成。 输入的第一行包含一个字符串 $S$ ,表示旧密码。 您可以假设$S$的长度不小于$1$且不大于$10$。 请注意,旧密码 $S$ 可能包含两次或更多次相同的数字,并且可能有前导零。

输出

打印一行新密码。



示例输入 1

201

样本输入 1 的输出

701

示例输入 2

512

样本输入 2 的输出

012

示例输入 3

99999

样本输入 3 的输出

49876

示例输入 4

765876346

样本输入 4 的输出

265874931