fork download
copy 
  1. program mountain;
  2. Uses sysutils, Math;
  3.  
  4. const
  5.     MAXN = 100005;
  6. Type elenco= Array of LongInt;
  7. var
  8.     ANS, N, i, j,id,x, maxMountainLength, lung, len, ricordamaxmount : LongInt;
  9.     P, leftLIS, rightLIS : Array[0..MAXN-1] of LongInt;
  10.     LIS : elenco;
  11.     rimossi : Ansistring;
  12.     uscita : boolean;
  13.  
  14.  
  15. Procedure ricercaUpper (var w:elenco; target:Longint); (*ritorna indice del valore maggiore/uguale a target oppure -1 se non esiste*)
  16.   var m,start,eend: Longint;
  17.  
  18.  begin  
  19.    start:=0; eend:=len-1 ; m:=-1;
  20.    while start<=eend do
  21.            begin
  22.                   m:=(start + eend) div 2;
  23.                   if w[m]<target then  start:=m+1
  24.                                  else  if w[m]>=target then  begin id:=m;  eend:=m-1 end;
  25.            end;
  26.    if start=len then id:=-1;
  27.  
  28.  end;
  29.  
  30.  
  31.  
  32.  
  33. begin
  34.     (*assign(input,  'input.txt');  reset(input);
  35.     assign(output, 'output.txt'); rewrite(output);*)  
  36.  
  37.     ReadLn(N);
  38.     rimossi:=''; lung:=N; 
  39.     for i:=0 to N-1 do begin
  40.                         Read(P[i]);
  41.                         rimossi:=rimossi+IntTostr(P[i]);
  42.                        end;  
  43.     ReadLn();
  44.     ANS := 0; ricordamaxmount:=0;
  45. 				(*leftLIS[i] stores the length of longest increasing subsequence ending at index i*)
  46. 				(*rightLIS[i] stores the length of longest decreasing subsequence starting at index i*)
  47.     		len:=1; SetLength(LIS,len); LIS[0]:=P[0];
  48. 		for i:=0 to  lung-1 do begin leftLIS[i]:=1; rightLIS[i]:=1; end;
  49. 				 (*Calculate LIS from left to right for each position*)
  50. 		for i :=1 to lung-1 do
  51.                     begin
  52.                         ricercaUpper(Lis, P[i]);
  53.                        // if element is to be inserted in lis
  54.  
  55.                         if (id <>-1) and (id<>0)  then
  56.                                       begin
  57.                                         LIS[id] := P[i];
  58.                                         leftLIS[i]:=id+1;
  59.                                       end 
  60.                        // if element in not present in lis insert at the end
  61.                                     else
  62.                                       if id=-1 then
  63.                                                  begin
  64.                                        			 len:=len+1;
  65.                                       			 SetLength(LIS,len);
  66.                                        			 LIS[len-1] := P[i];
  67.                                        			 leftLIS[i]:=len;
  68.                                                   end; 
  69.                     end; 
  70.  
  71.     				 (* Calculate LIS from right to left (decreasing subsequence) for each position*)
  72.  
  73. 			len:=1; SetLength(LIS,len); LIS[0]:=P[N-1]; 
  74. 			for i :=lung-2  downto 0 do
  75.                     begin
  76.                         ricercaUpper(Lis, P[i]);
  77.  
  78.                        // if element is to be inserted in lis
  79.  
  80.                         if (id <>-1) and (id<>0)  then
  81.                                       begin
  82.                                         LIS[id] := P[i];
  83.                                         rightLIS[i]:=id+1;
  84.                                       end 
  85.                        // if element in not present in lis insert at the end
  86.                                     else
  87.                                       if id=-1 then
  88.                                       begin
  89.                                        len:=len+1;
  90.                                        SetLength(LIS,len);
  91.                                        LIS[len-1] := P[i];
  92.                                        rightLIS[i]:=len;
  93.                                       end; 
  94.                     end;
  95.  
  96.     			maxMountainLength := 0;
  97.     		(* Find the maximum length of mountain subsequence*)
  98.     		// for every index check for longest mountain array,
  99.     			for i := 0 to lung-1 do
  100.             		 begin
  101.             		   if (leftLIS[i] >=1) AND (rightLIS[i] >= 1) then 
  102.                               begin
  103.                                 x := leftLIS[i] + rightLIS[i] - 1;
  104.                                 maxMountainLength := max(maxMountainLength, x);
  105.                               end;  
  106.             		 end;
  107. 				 // returning removals
  108.     if maxMountainLength>ricordamaxmount then ricordamaxmount:=maxMountainLength;
  109.     uscita:=false;  
  110.     while uscita=false do 
  111.        begin
  112.         j:=2; uscita:=true;
  113.         while j<lung do
  114.               begin
  115.                 if  (rimossi[j]<rimossi[j-1]) and (rimossi[j]<rimossi[j+1])                    
  116.                                       then
  117.                                            begin
  118.                                                 delete(rimossi,j,1);
  119.                                                 lung:=lung-1; 
  120.                                                 setLength(rimossi,lung);
  121.                                                 uscita:=false;                                                                                        
  122.                                             end;
  123.                 for i:=1 to lung  do P[i-1]:=StrToInt(rimossi[i]);
  124.                 ANS := 0; 
  125. 				(*leftLIS[i] stores the length of longest increasing subsequence ending at index i*)
  126. 				(*rightLIS[i] stores the length of longest decreasing subsequence starting at index i*)
  127.     		len:=1; SetLength(LIS,len); LIS[0]:=P[0];
  128. 		for i:=0 to  lung-1 do begin leftLIS[i]:=1; rightLIS[i]:=1; end;
  129. 				 (*Calculate LIS from left to right for each position*)
  130. 		for i :=1 to lung-1 do
  131.                     begin
  132.                         ricercaUpper(Lis, P[i]);
  133.                        // if element is to be inserted in lis
  134.  
  135.                         if (id <>-1) and (id<>0)  then
  136.                                       begin
  137.                                         LIS[id] := P[i];
  138.                                         leftLIS[i]:=id+1;
  139.                                       end 
  140.                        // if element in not present in lis insert at the end
  141.                                     else
  142.                                       if id=-1 then
  143.                                                  begin
  144.                                        			 len:=len+1;
  145.                                       			 SetLength(LIS,len);
  146.                                        			 LIS[len-1] := P[i];
  147.                                        			 leftLIS[i]:=len;
  148.                                                   end; 
  149.                     end; 
  150.  
  151.     				 (* Calculate LIS from right to left (decreasing subsequence) for each position*)
  152.  
  153. 			len:=1; SetLength(LIS,len); LIS[0]:=P[N-1]; 
  154. 			for i :=lung-2  downto 0 do
  155.                     begin
  156.                         ricercaUpper(Lis, P[i]);
  157.  
  158.                        // if element is to be inserted in lis
  159.  
  160.                         if (id <>-1) and (id<>0)  then
  161.                                       begin
  162.                                         LIS[id] := P[i];
  163.                                         rightLIS[i]:=id+1;
  164.                                       end 
  165.                        // if element in not present in lis insert at the end
  166.                                     else
  167.                                       if id=-1 then
  168.                                       begin
  169.                                        len:=len+1;
  170.                                        SetLength(LIS,len);
  171.                                        LIS[len-1] := P[i];
  172.                                        rightLIS[i]:=len;
  173.                                       end; 
  174.                     end;
  175.  
  176.     			maxMountainLength := 0;
  177.     		(* Find the maximum length of mountain subsequence*)
  178.     		// for every index check for longest mountain array,
  179.     			for i := 0 to lung-1 do
  180.             		 begin
  181.             		   if (leftLIS[i] >=1) AND (rightLIS[i] >= 1) then 
  182.                         begin
  183.                           x := leftLIS[i] + rightLIS[i] - 1;
  184.                           maxMountainLength := max(maxMountainLength, x);
  185.                         end;  
  186.             		 end;
  187. 				 // returning removals
  188.                     if maxMountainLength>ricordamaxmount then ricordamaxmount:=maxMountainLength;
  189.  
  190.  
  191.                 j:=j+1;
  192.               end;              
  193.        end; 
  194.        ANS:= N - ricordamaxmount;  
  195.    WriteLn(ANS);
  196. end.
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6
2 3 0 5 1 4
stdout
copy 
2
https://ideone.com/70h0iw
language:
Pascal (fpc 3.0.4)
created:
3 days 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!