能被15整除的最大整数 BITOJ 网络教室

能被15整除的最大整数

成绩: 5 / 折扣: 0.8

给定一个只包含数字 [0..9] 的字符串，求使用字符串中的某些字符，构造一个能够被15整除的最大整数。注意，字符串中的每个字符只能使用一次。
输入：程序从标准输入读入数据，每行数据由一串数字组成，长度为1到1000。
输出：针对每一行输入，输出一个结果，每个结果占一行。如果无法构造出能够被15整除的整数，请输出impossible。

	测试输入	期待的输出	时间限制	内存限制	额外进程
测试用例 1	1↵ 01431↵	impossible↵ 43110↵

思路，题目有意降低难度，为什么是15 而不是18 16 之类的，因为，15=3*5，这个就好办了。学过数论的都知道：

定理：如果15可以整除X（即X是15的倍数），那么5也可整除X，3也可以整除X。于是这道题目就变得简单。

5整除X，于是，X的末尾只能是0或者5。

3整除X，于是所有的数字之和必须是3的倍数。这就是为什么题目出一个15。

说一下思路：用cnt数组存放每个字符（0~9）出现的次数。stack存放，mod=1 、2 的数字是哪些，排个序存放。

然后，先用上所有的数字，不满足的话，一个个剔除。从小到大剔除，遍历所有剔除的方案，还是不满足，直接impossible。

ps：15可以整除0.，笔者因为介个，WA了N次。

欢迎转载，著名出处。