C1576 [Contest #11]A-eon

内存限制:256 MB 时间限制:1000 ms

题目描述

※ 简洁题意在分隔线下方

「这次练习用的数也太大了吧,我怎么记得住。」线段树小声嘀咕着,「我用所有的手指也只能数到 $1023$ 。」

「这可不是数据结构会作出的发言。」链表指引着面前的少女把数写进她的本体——一棵二叉树的图样中。有光自最浅的节点倾泻而下。「接下来你应该把这个十进制数按数位拆开,重新排列出一个最大的数,然后算出这个数和原数的差。」她正要问线段树是否听懂了任务,却被线段树的发问打断了。

「上一代数据结构,他们会区间排序,能轻松地击溃那些题目,是这样吗?他们于代码的溪流中降生,在算法的庇佑下抽枝长叶,以天赐的技巧征服了我们一代至今无法涉足的外界,是这样吗?」

链表沉默半晌,转移了话题:「你还不会输出,那便直接告诉我练习的答案对$10$ 取模的值。」

你对这个种族的历史毫无兴趣,只想知道练习题的答案,也就是说——




简洁题意:

对于一个数 $n$ ,记 $m$ 为把 $n$ 的各数位重排序得到的最大的数,求 $m-n$ 对 $10$ 取模的值(也就是 $m-n$ 除以 $10$ 的余数)。

举例来说,当 $n = 213$ 时, 各数位重排序有 $123$、$132$、$213$、$231$、$312$、$321$ 六种可能,其中最大的数字是 $321$ ,所以 $m=321$,输出的答案即为 $(m-n) = 108$ 对 $10$ 取模的结果,也就是 $8$。

输入格式

一行一个整数 $n$ ($0\lt n \lt 10^{10^6}$,也就是说 $n$ 是位数不超过 $10^6$ 的正整数。)。

输出

一个整数,表示答案。

样例

样例输入 1

213

样例输出 1

8

样例输入 2

71806291

样例输出 2

9

样例输入 3

12345678912345678912345

样例输出 3

6

提示