k-平滑集

题目内容

题目描述

当一个集合满足对于任意一对集合的元素(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中选择的最大子集的大小。

样例输入

4 4 10 5 6 2

样例输出

3

提示

提交评测
请登录后再操作

题目描述

k-平滑集
1125
0
Level2
126
65
52%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在