fork download
  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+=2 )
  190. {
  191. ret = min( ret , Cal( x , i ) + DP( x + 1 , i - 1 ) + 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. //for ( int i = 4 ; i <= 30 ; i += 4 ) cout << binary( i ) << endl ;
  202. /* int p = lower_bound( prime , prime + id , 4 ) - prime ;
  203.   cout << prime[ p ] << endl ;
  204.   p = lower_bound( prime , prime + id , 5 ) - prime ;
  205.   cout << prime[p] << endl ; */
  206. while( scanf("%d",&n) == 1)
  207. {
  208. ms( dp , -1 );
  209. rep( i , n ) inp[ i ] = II ;
  210. printf("%lld\n",DP( 0 , n - 1 ) );
  211. }
  212.  
  213.  
  214.  
  215.  
  216. return 0;
  217. }
  218.  
Success #stdin #stdout 0.04s 44520KB
stdin
Standard input is empty
stdout
Standard output is empty