Advertisement
Guest User

Untitled

a guest
Dec 8th, 2013
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1. #include <bits/stdc++.h>/*{{{*/
  2. using namespace std;typedef long long ll;typedef long double ld;void run();int main(){ios::sync_with_stdio(0);run();}/*}}}*/
  3.  
  4. set<int> prime_factors(int n){
  5.   set<int> res;
  6.   for (int i=2; i*i<=n; i++){
  7.     if (n%i==0){
  8.       res.insert(i);
  9.       while (n%i==0) n/=i;
  10.     }
  11.   }
  12.   if (n>1) res.insert(n);
  13.   return res;
  14. }
  15.  
  16. bool is_prime(int n){
  17.   for (int i=2; i*i<=n; i++) if (n%i==0) return false;
  18.   return true;
  19. }
  20.  
  21. int gcd(int a,int b){return b?gcd(b,a%b):a;}
  22.  
  23. void run(){
  24.   int tsts; cin>>tsts; for (int tst=1; tst<=tsts; ++tst){
  25.     cerr<<"running test "<<tst<<" of "<<tsts<<endl;
  26.  
  27.     int n,k; cin>>n>>k;
  28.     vector<int> val(n); for (auto &i: val) cin>>i; sort(val.rbegin(),val.rend());
  29.     if (val.back()==0) val.pop_back(), --n;
  30.     sort(val.begin(),val.end());
  31.  
  32.     int sof[50]={};
  33.     for (int i=0; i<n; i++) sof[i+1]=sof[i]+val[i];
  34.  
  35.     int agn[50]={};
  36.     int best=0;
  37.     for (int i=0,j=1; i<n; i++){
  38.       if (val[i]>1){
  39.         do j++; while (j*k<val[i] or not is_prime(j));
  40.       }
  41.       best+=j*k-val[i];
  42.       agn[i]=j;
  43.     }
  44.     for (int aug=1; aug--;){
  45.       for (int i=n; i--;){
  46.         for (int j=max(1,(val[i]+k-1)/k); j<agn[i]; j++){
  47.           bool ok=true;
  48.           for (int k=n; k--;) if (k!=i and gcd(agn[k],j)>1) {ok=false;break;}
  49.           if (ok){
  50.             best+=k*(j-agn[i]);
  51.             agn[i]=j;
  52.             aug=1;
  53.             break;
  54.           }
  55.         }
  56.       }
  57.       sort(agn,agn+n);
  58.     }
  59.  
  60.     map<vector<int>,int> dp[30];
  61.     dp[0][vector<int>()]=0;
  62.  
  63.     vector<int> pf[1000];
  64.     for (int i=1; i<=500; i++){
  65.       set<int> pfs=prime_factors(i);
  66.       for (auto j: pfs) pf[i].push_back(j);
  67.     }
  68.  
  69.     for (int i=0; i<n; i++){
  70.       for (int x=max(1,(val[i]+k-1)/k); x<=500; x++){
  71.  
  72.         for (pair<vector<int>,int> const &j: dp[i]){
  73.           if (j.second+x*k*(n-i)-(sof[n]-sof[i])>=best) continue;
  74.           int cost=j.second+x*k-val[i];
  75.  
  76.           bool ok=true;
  77.           for (auto q: pf[x]) if (binary_search(j.first.begin(),j.first.end(),q)) {ok=false;break;}
  78.           if (not ok) continue;
  79.  
  80.           vector<int> all=j.first;
  81.           for (auto q: pf[x]) all.push_back(q);
  82.           sort(all.begin(),all.end());
  83.  
  84.           if (not dp[i+1].count(all) or dp[i+1][all]>cost) dp[i+1][all]=cost;
  85.         }
  86.       }
  87.     }
  88.  
  89.     int res=best;
  90.     for (auto i: dp[n]) res=min(res,i.second);
  91.     if (res==best) cerr<<" answer = bruteforce"<<endl;
  92.     cout<<"Case #"<<tst<<": "<<res<<endl;
  93.   }
  94.   cerr<<"finished"<<endl;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement