fork download
copy 
  1. #include <cstdlib>
  2. #include <cstdio>
  3.  
  4. const int m=65536;
  5. const int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
  6. int n,a,t,s[59];
  7. int f[109][m],g[109][m];
  8. int c,b[109];
  9.  
  10. int main()
  11. {
  12.  scanf("%d",&n);
  13.  for (int i=1;i<59;++i) for (int j=0;j<16;++j) if (i%p[j]==0) s[i]|=1<<j;
  14.  for (int j=1;j<m;++j) f[0][j]=0X40000000;
  15.  for (int i=1;i<=n;++i)
  16.  {
  17.   scanf("%d",&a);
  18.   for (int j=0;j<m;++j) f[i][j]=0X40000000;
  19.   for (int j=0;j<m;++j)
  20.   {
  21.    for (int k=1;k<59;++k) if (!(j&s[k]))
  22.    {
  23.     t=j|s[k];
  24.     if (f[i][t]>f[i-1][j]+abs(k-a))
  25.     {
  26.      f[i][t]=f[i-1][j]+abs(k-a);
  27.      g[i][t]=k;
  28.     }
  29.    }
  30.   }
  31.  }
  32.  for (int j=0;j<m;++j) if (f[n][t]>f[n][j]) t=j;
  33.  for (int i=n;i;--i) t^=s[b[c++]=g[i][t]];
  34.  while (c--) printf("%d ",b[c]);
  35.  return 0;
  36. }
Success #stdin #stdout 0.27s 14672KB
comments (?)
stdin
copy 
26 
 3 3 5 5 5 7 8 8 8 8 9  10 11 11 13 14 14 14 14 15 23 24 25 26 27 28
stdout
copy 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 16 7 11 13 17 19 23 25 27 29 31
https://ideone.com/VUyN5p
language:
C++14 (gcc 8.3)
created:
4 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!