fork download
copy 
  1. #include<cstdio>
  2. #include<set>
  3. #include<vector>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long int ll;
  8.  
  9. ll k, n, c;
  10.  
  11. multiset<ll> s;
  12.  
  13. vector< multiset<ll> :: iterator> v;
  14.  
  15. inline void initialize(){
  16.     s.clear();
  17.     v.clear();
  18.     return;
  19. }
  20.  
  21. ll inf = 1e18 + 3;
  22.  
  23. bool safe_mul(ll a, ll b){
  24.     if(a <= inf/b) return true;
  25.     return false;
  26. }
  27.  
  28. void remove_used(){
  29.     for(int j=0; j<k; j++)
  30.         s.erase(v[j]);
  31.     return;
  32. }
  33.  
  34. ll check(ll a){
  35.     multiset<ll> :: iterator it;
  36.     it = s.lower_bound(a);
  37.     if(it == s.end()) return -1;
  38.     v.push_back(it);
  39.     return *it;
  40. }
  41.  
  42. bool IsPoss(){
  43.     if(s.size() < k) return false;
  44.     ll start = *(s.begin());
  45.     v.clear();
  46.     v.push_back(s.begin());
  47.     if(!safe_mul(start, c)) return false;
  48.     ll curr = start*c;
  49.     for(int j=1; j<k; j++){
  50.         ll temp = check(curr);
  51.         if(temp == -1) return false;
  52.         if(!safe_mul(temp, c)) return false;
  53.         curr = temp*c;
  54.     }
  55.     remove_used();
  56.     return true;
  57. }
  58.  
  59. void solve(){
  60.     ll ans = 0;
  61.     while(IsPoss())
  62.         ans++;
  63.     printf("%lld\n",ans);
  64.     return;
  65. }
  66.  
  67. int main(){
  68.     int t;
  69.     scanf("%d",&t);
  70.     while(t--){
  71.         initialize();
  72.         scanf("%lld %lld %lld",&n ,&k ,&c);
  73.         for(int j=0; j<n; j++){
  74.             ll temp;
  75.             scanf("%lld",&temp);
  76.             s.insert(temp);
  77.         }
  78.         solve();
  79.     }
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1
8 3 2
1 2 2 4 1 2 3 4
stdout
copy 
2
https://ideone.com/FUiT5q
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!