当一个集合满足对于任意一对集合的元素(A, B),都满足A <= k * B时,这个集合就被称为k-平滑集。举个例子,集合{3, 4, 7, 9}是一个3-平滑集,但是集合{30, 60, 100}不是3-平滑集:100是大于3 * 30的。
Hero喜欢某些整数构成的集合。Hero采用如下的方式来确认是否喜欢某个集合S:使用集合S任意两个元素的差的绝对值,构造一个新的集合D,换句话说,也就是对于集合S的每一对元素(A, B),将|A-B|放入集合D。
如果集合D是k-平滑集,那么Hero就喜欢集合S。
现在给出一个由整数构成的集合a,a中包含n(2 <= n <= 50)个整数,这些整数各不相同,并给出k。请你求出a的所有子集中,能使Hero喜欢的,最大的子集。
输入第一行为一个正整数n,代表集合a中元素的个数。
接下来一行包含n个正整数,每个正整数的大小不超过10的9次方,正整数之间以空格隔开。代表集合a的各个元素。
最后一行为一个整数k,代表题目要求集合是k-平滑的。
输出一个整数,代表能在集合a中选择的最大子集的大小。
请输入正确的证书编号
学员姓名:孙兴民
课程:Scratch Level 1
发证日期:2019.08.15