1085. Perfect Sequence (25)

Given a sequence of positive integers and another positive integer p. The sequence is said to be a "perfect sequence" if M <= m * p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (<= 10⁵) is the number of integers in the sequence, and p (<= 10⁹) is the parameter. In the second line there are N positive integers, each is no greater than 10⁹.

Output Specification:

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:

10 8
2 3 20 4 5 1 6 7 8 9

Sample Output:

 1 #include<stdio.h>
 2 #include<vector>
 3 #include<algorithm>
 4 using namespace std;
 5 int main()
 6 {
 7     long long len,p,i,tem,j;
 8     vector<long long> vv;
 9     scanf("%lld%lld",&len,&p);
10     for(i = 0;i<len;i++)
11     {
12         scanf("%lld",&tem);
13         vv.push_back(tem);
14     }
15 
16     sort(vv.begin(),vv.end());
17 
18     int Max= 0;
19     int count;
20     i = 0; j = 0;
21     for(i = 0 ; i < len ;i ++)
22     {
23         j = i + Max;
24         count = Max;
25         while( j < len && vv[j] <= vv[i] * p)
26         {
27             ++j;
28             ++ count;
29         }
30         if(Max < count) Max = count;
31     }
32     printf("%d
",Max);
33     return 0;
34 }