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, id,x, maxMountainLength,  len : 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.     for i:=0 to N-1 do Read(P[i]);
  39.     ReadLn();
  40.  
  41.  
  42.     ANS := 0; 
  43. 	(*leftLIS[i] stores the length of longest increasing subsequence ending at index i*)
  44. 	(*rightLIS[i] stores the length of longest decreasing subsequence starting at index i*)
  45.     len:=1; SetLength(LIS,len); LIS[0]:=P[0];
  46.     for i:=0 to  N-1 do begin leftLIS[i]:=1; rightLIS[i]:=1; end;
  47.     (*Calculate LIS from left to right for each position*)
  48.     for i :=1 to N-1 do
  49.                     begin
  50.                         ricercaUpper(Lis, P[i]);
  51.                        // if element is to be inserted in lis
  52.  
  53.                         if (id <>-1) and (id<>0)  then
  54.                                       begin
  55.                                         LIS[id] := P[i];
  56.                                         leftLIS[i]:=id+1;
  57.                                       end 
  58.                        // if element in not present in lis insert at the end
  59.                                     else
  60.                                       if id=-1 then
  61.                                                  begin
  62.                                        			  len:=len+1;
  63.                                       			  SetLength(LIS,len);
  64.                                        			  LIS[len-1] := P[i];
  65.                                        			  leftLIS[i]:=len;
  66.                                                   end; 
  67.                     end; 
  68.  
  69.        (* Calculate LIS from right to left (decreasing subsequence) for each position*)
  70.    for i:=0 to len-1 do write(LIS[i],' '); writeln;    
  71.    len:=1; SetLength(LIS,len); LIS[0]:=P[N-1]; 
  72.    for i :=N-2  downto 0 do
  73.                     begin
  74.                         ricercaUpper(Lis, P[i]);
  75.  
  76.                        // if element is to be inserted in lis
  77.  
  78.                         if (id <>-1) and (id<>0)  then
  79.                                       begin
  80.                                         LIS[id] := P[i];
  81.                                         rightLIS[i]:=id+1;
  82.                                       end 
  83.                        // if element in not present in lis insert at the end
  84.                                     else
  85.                                       if id=-1 then
  86.                                       begin
  87.                                        len:=len+1;
  88.                                        SetLength(LIS,len);
  89.                                        LIS[len-1] := P[i];
  90.                                        rightLIS[i]:=len;
  91.                                       end; 
  92.                     end;
  93.     for i:=0 to len-1 do write(LIS[i],' '); writeln;        
  94.     maxMountainLength := 0;
  95.     (* Find the maximum length of mountain subsequence*)
  96.     // for every index check for longest mountain array,
  97.     for i := 0 to N-1 do
  98.              begin
  99.                 if (leftLIS[i] >=1) AND (rightLIS[i] >= 1) then 
  100.                       begin
  101.                         x := leftLIS[i] + rightLIS[i] - 1;
  102.                         maxMountainLength := max(maxMountainLength, x);
  103.                       end;  
  104.              end;
  105.     // returning removals
  106.  
  107.    ANS:= N - maxMountainLength; 
  108.    WriteLn(ANS);
  109. end.
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
8
0 1 7 5 4 6 2 3
stdout
copy 
0 1 2 3 
3 4 5 7 
2
https://ideone.com/59H8pl
language:
Pascal (fpc 3.0.4)
created:
2 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!