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, maxMountainLength, lung, 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:=lung-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=lung then id:=-1;
  27.  end;
  28.  
  29.  
  30.  
  31.  
  32. begin
  33.     (*assign(input,  'input.txt');  reset(input);
  34.     assign(output, 'output.txt'); rewrite(output);*)  
  35.  
  36.     ReadLn(N);
  37.     rimossi:=''; lung:=N; 
  38.     for i:=0 to N-1 do begin
  39.                         Read(P[i]);
  40.                         rimossi:=rimossi+IntTostr(P[i]);
  41.                        end;  
  42.     ReadLn();
  43.     i:=2; uscita:=false;
  44.     while uscita=false do 
  45.        begin
  46.         i:=2; uscita:=true;
  47.         while i<lung do
  48.               begin
  49.                 if  (rimossi[i]<rimossi[i-1]) and (rimossi[i]<rimossi[i+1])                    
  50.                                       then
  51.                                            begin
  52.                                                 delete(rimossi,i,1);
  53.                                                 lung:=lung-1;  
  54.                                                 uscita:=false;                                          
  55.                                             end;
  56.                 i:=i+1;
  57.               end;              
  58.        end;     
  59.     for i:=1 to lung  do P[i-1]:=StrToInt(rimossi[i]); 
  60.  
  61.     ANS := 0; 
  62. 	(*leftLIS[i] stores the length of longest increasing subsequence ending at index i*)
  63. 	(*rightLIS[i] stores the length of longest decreasing subsequence starting at index i*)
  64.     len:=1; SetLength(LIS,len); LIS[0]:=P[0];
  65.     for i:=0 to  lung-1 do begin leftLIS[i]:=1; rightLIS[i]:=1; end;
  66.     (*Calculate LIS from left to right for each position*)
  67.     for i :=0 to lung-1 do
  68.                     begin
  69.                         ricercaUpper(Lis, P[i]);
  70.                        // if element is to be inserted in lis
  71.                        writeln(i,' ',P[i],' ',id,' ');
  72.                         if id <>-1 then
  73.                                       begin
  74.                                         LIS[id] := P[i];
  75.                                         leftLIS[i]:=id+1;
  76.                                       end 
  77.                        // if element in not present in lis insert at the end
  78.                                     else
  79.                                       begin
  80.                                        len:=len+1;
  81.                                        SetLength(LIS,len);
  82.                                        LIS[len-1] := P[i];
  83.                                        leftLIS[i]:=len;
  84.                                       end; 
  85.                     end;
  86.        (* Calculate LIS from right to left (decreasing subsequence) for each position*)
  87.    for i:=0 to len-1 do write(LIS[i],' '); writeln; 
  88.    len:=1; SetLength(LIS,len); LIS[0]:=P[N-1];
  89.    for i :=lung-1  downto 0 do
  90.                     begin
  91.                         ricercaUpper(Lis, P[i]);
  92.                        // if element is to be inserted in lis
  93.                         if id <>-1 then
  94.                                       begin
  95.                                         LIS[id] := P[i];
  96.                                         leftLIS[i]:=id+1;
  97.                                       end 
  98.                        // if element in not present in lis insert at the end
  99.                                     else
  100.                                       begin
  101.                                        len:=len+1;
  102.                                        SetLength(LIS,len);
  103.                                        LIS[len] := P[i];
  104.                                        leftLIS[i]:=len;
  105.                                       end; 
  106.                     end;
  107.                     for i:=0 to len-1 do write(LIS[i],' '); writeln; 
  108.     maxMountainLength := 0;
  109.     (* Find the maximum length of mountain subsequence*)
  110.     // for every index check for longest mountain array,
  111.     for i := 1 to lung-1 do
  112.              begin
  113.                 if (leftLIS[i] > 1) AND (rightLIS[i] > 1) then 
  114.                       begin
  115.                         ans := leftLIS[i] + rightLIS[i] - 1;
  116.                         maxMountainLength := max( maxMountainLength, ans);
  117.                       end;  
  118.              end;
  119.     // returning removals
  120.  
  121.    ANS:= N - maxMountainLength; 
  122.    WriteLn(ANS);
  123. end.
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
6
2 3 0 5 1 4
stdout
copy 
0 2 2 
1 3 -1 
2 5 -1 
3 4 2 
2 3 4 
4 0 
6
https://ideone.com/LZ0MkL
language:
Pascal (fpc 3.0.4)
created:
1 day 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!