fork download
copy 
  1. //BISMILLAHIRRAHMANIRRAHIM
  2. /*
  3.  manus tar shopner soman boro
  4.  all my suceesses are dedicated to my parents
  5.  The true test of a man's character is what he does when no one is watching.
  6.  
  7.  
  8.  Author :: Shakil Ahmed
  9. .............AUST_CSE27.........
  10.  prob   ::
  11.  Type   ::
  12.  verdict::
  13.  */
  14.  
  15. #include <bits/stdc++.h>
  16. #define pb push_back
  17. #define mp make_pair
  18.  
  19. // Macro
  20. #define eps 1e-9
  21. #define pi acos(-1.0)
  22. #define ff first
  23. #define ss second
  24. #define re return
  25. #define QI queue<int>
  26. #define SI stack<int>
  27. #define SZ(x) ((int) (x).size())
  28. #define all(x) (x).begin(), (x).end()
  29. #define sq(a) ((a)*(a))
  30. #define distance(a,b) (sq(a.x-b.x) + sq(a.y-b.y))
  31. #define iseq(a,b) (fabs(a-b)<eps)
  32. #define eq(a,b) iseq(a,b)
  33. #define ms(a,b) memset((a),(b),sizeof(a))
  34. #define G() getchar()
  35. #define MAX3(a,b,c) max(a,max(b,c))
  36. #define II ( { int a ; read(a) ; a; } )
  37. #define LL ( { Long a ; read(a) ; a; } )
  38. #define DD ({double a; scanf("%lf", &a); a;})
  39.  
  40. double const EPS=3e-8;
  41. using namespace std;
  42.  
  43. #define FI freopen ("input.txt", "r", stdin)
  44. #define FO freopen ("output.txt", "w", stdout)
  45.  
  46. typedef long long Long;
  47. typedef long long int64;
  48. typedef unsigned long long ull;
  49. typedef vector<int> vi ;
  50. typedef set<int> si;
  51. typedef vector<Long>vl;
  52. typedef pair<int,int>pii;
  53. typedef pair<string,int>psi;
  54. typedef pair<Long,Long>pll;
  55. typedef pair<double,double>pdd;
  56. typedef vector<pii> vpii;
  57.  
  58. // For loop
  59.  
  60. #define forab(i, a, b)	for (__typeof (b) i = (a) ; i <= b ; ++i)
  61. #define rep(i, n)		forab (i, 0, (n) - 1)
  62. #define For(i, n)		forab (i, 1, n)
  63. #define rofba(i, a, b)	for (__typeof (b)i = (b) ; i >= a ; --i)
  64. #define per(i, n)		rofba (i, 0, (n) - 1)
  65. #define rof(i, n)		rofba (i, 1, n)
  66. #define forstl(i, s)	for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
  67.  
  68. template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
  69. template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
  70.  
  71. //Fast Reader
  72. template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;}
  73.  
  74. //int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
  75. //int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
  76. //int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
  77. //int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
  78.  
  79. /* **************************************  My code start here ****************************************** */
  80.  
  81.  
  82. const int NX = 2e6 + 10 ;
  83.  
  84. int check[ NX ] , id , inp[ NX ] , ID[ NX ] ;
  85. Long prime[ NX ] ;
  86. void ini()
  87. {
  88.     int i , j ;
  89.     id = 0 ;
  90.     prime[ id++ ] = 2 ;
  91.     ID[ 2 ] = id ;
  92.     check[ 1 ] = -1 ;
  93.     check[ 2 ] = 1 ;
  94.     //for ( int i = 4 ; i < NX ; i += 2 ) check[i] = -1 ;
  95.   //  int i ;
  96.     for ( i = 3 ; i * i < NX ; i += 2 )
  97.     {
  98.         if( check[i] == 0 )
  99.         {
  100.             prime[ id++ ] = i ;
  101.             ID[ i ] = id ;
  102.             check[ i ] = 1 ;
  103.             for ( int j = i * i ; j < NX ; j += ( i + i ) ) check[ j ] = -1 ;
  104.         }
  105.     }
  106.     while( i < NX )
  107.     {
  108.         if( check[i] == 0 )
  109.         {
  110.             check[i] = 1 ;
  111.             prime[id++] = i ;
  112.             ID[ i ] = id ;
  113.         }
  114.         i += 2 ;
  115.     }
  116.    /* for ( int i = 1 ; i <= 50 ; i++ )
  117.     {
  118.         if( check[i] == 1 ) printf(" %d -> %d\n" , i , ID[i] );
  119.     } */
  120.  
  121. }
  122. int n ; Long dp[ 505 ][ 505 ];
  123. Long binary( int val )
  124. {
  125.     int low = 0 , high = id - 1 , mid ;
  126.     Long ans = ( 1e16) ;
  127.     while( low <= high )
  128.     {
  129.         int mid = ( low + high )/2 ;
  130.         if( prime[ mid ] < val )
  131.         {
  132.             ans = prime[ mid ];
  133.             low = mid + 1 ;
  134.  
  135.         }
  136.         else high = mid - 1 ;
  137.     }
  138.     return ans ;
  139. }
  140. Long Cal( int x , int y )
  141. {
  142.         // special case
  143.         //if( inp[ y ] == 2 && inp[ x ] == 1 ) return ( 3 );
  144.         //if( inp[x] == 2 && inp[y] == 1 ) return ( 3 );
  145.         if( check[ inp[x] ] == 1 && check[ inp[y]] == 1 )
  146.         {
  147.             if( ID[ inp[y] ] - ID[ inp[ x ] ] == 1 ) return 1 ;
  148.         }
  149.  
  150.         if( inp[ y ] > inp[ x ] )
  151.         {
  152.             Long A = binary( inp[y] ) ;
  153.             if( A < inp[x] || A == ( 1e16) )
  154.             {
  155.                 int p = lower_bound( prime , prime + id , inp[x] ) - prime ;
  156.                 Long a = prime[ p ] - inp[ x ];
  157.                 p = lower_bound ( prime , prime + id , prime[ p ] + 1 ) - prime ;
  158.                 Long b = prime[ p ] - inp[ y ];
  159.                return a + b ;
  160.             }
  161.             A -= inp[ x ];
  162.  
  163.             int p = lower_bound( prime , prime + id , inp[y] ) - prime ;
  164.             A = A + ( prime[p] - inp[y] ) ;
  165.  
  166.             return A ;
  167.         }
  168.  
  169.  
  170.         int p = lower_bound( prime , prime + id , inp[x] ) - prime ;
  171.         Long a = prime[ p ] - inp[ x ];
  172.         p = lower_bound ( prime , prime + id , prime[ p ] + 1 ) - prime ;
  173.  
  174.         Long b = prime[ p ] - inp[ y ];
  175.         return a + b  ;
  176.  
  177. }
  178. Long DP( int x , int y )
  179. {
  180.     if( x > y ) return 0 ;
  181.     if( x + 1 == y )
  182.     {
  183.         return Cal( x , y ) + 1;
  184.     }
  185.     Long &ret = dp[ x ][ y ];
  186.     if( ret != -1 ) return ret ;
  187.     ret = Cal( x , y ) + DP( x + 1 , y - 1 ) + 1;
  188.     int i ;
  189.     for ( i = x + 1 ; i < y - 1  ; i++ )
  190.     {
  191.         ret = min( ret , DP( x , i ) + DP( i + 1 , y ) + 1 );
  192.     }
  193.     return ret ;
  194.  
  195. }
  196. int main()
  197. {
  198.    // I will always use scanf and printf
  199.    // May be i won't be a good programmer but i will be a good human being
  200.     ini();
  201.  
  202.     while( scanf("%d",&n) == 1)
  203.     {
  204.         ms( dp , -1 );
  205.         rep( i , n ) inp[ i ] = II ;
  206.         printf("%lld\n",DP( 0 , n - 1 ) );
  207.     }
  208.  
  209.  
  210.  
  211.  
  212.     return 0;
  213. }
  214.  
Success #stdin #stdout 0.04s 44512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ixIo9W
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!