fork download
copy 
  1. Program sairsodo;
  2. const MAXN=100000; 
  3. type elenco = array[1..MaXN] of int64;
  4. var N,i,d, idmediana, idmediana1, mediana:int64;
  5.     calcolacosto,calcolacosto1, altezzainiziale, altezzainiziale1:int64;
  6.     costo, costo1, costomin, ricordacostomin:int64;
  7.     H, ricordaltezze: elenco;
  8.     uscita, invariato:boolean;
  9.     ricordaintervallo:char;
  10. Procedure scambia (var a,b: int64);
  11. var x:int64;
  12. begin
  13.    x:=a;
  14.    a:=b;
  15.    b:=x;
  16. end;  
  17. Procedure ordinamento (estremoi,estremos:int64; var v : elenco; ordinato:boolean);
  18. var inf, sup, medio:int64;
  19.     pivot :int64;
  20. begin
  21.     inf:=estremoi;
  22.     sup:=estremos;
  23.     medio:= (estremoi+estremos) div 2;
  24.     pivot:=v[medio];
  25.     repeat
  26.       if (ordinato) then
  27.          begin
  28.             while (v[inf]<pivot) do  inf:=inf+1;
  29.             while (v[sup]>pivot) do  sup:=sup-1;
  30.          end;
  31.       if inf<=sup then
  32.        begin
  33.          scambia(v[inf],v[sup]);
  34.          inf:=inf+1;
  35.          sup:=sup-1;
  36.        end;
  37.     until inf>sup;
  38.     if (estremoi<sup) then ordinamento(estremoi,sup,v,ordinato);
  39.     if (inf<estremos) then ordinamento(inf,estremos,v,ordinato);
  40. end;
  41.  
  42. begin
  43.    (* assign(input,  'input.txt');  reset(input);
  44.     assign(output, 'output.txt'); rewrite(output);*)
  45. 	readln(N);
  46. 	for i:=1 to N do begin read(H[i]); ricordaltezze[i]:=H[i]; end;readln;
  47. 	costo:=0; costo1:=0; d:=0; ricordacostomin:=9223372036854775807; uscita:=false;
  48. 	ordinamento (1,N,H, true); 
  49. 	invariato:=false; ricordaintervallo:=' ';
  50. 	if N mod 2 <>0 then 
  51. 	                 begin
  52. 	                   idmediana:=(N+1) div 2;
  53. 	                   altezzainiziale:=H[idmediana]-(idmediana-1);
  54. 	                   if altezzainiziale<0 then altezzainiziale:=0;
  55. 	                   for i:=1 to N do
  56. 	                         begin 
  57. 	                             calcolacosto:=(ricordaltezze[i] - (altezzainiziale +i-1));
  58. 	                             if calcolacosto<0 then calcolacosto:=-calcolacosto;
  59. 	                             costo:= costo + calcolacosto ;
  60. 	                         end;
  61. 	                      writeln(costo);
  62. 	                end
  63. 	              else 
  64. 	               begin
  65. 	                idmediana:= N div 2;
  66. 	                idmediana1:=idmediana+1;
  67. 	                mediana:= (H[idmediana]+ H[idmediana + 1]) div 2; (*altezza che corrisponde alla mediana*)
  68. 	                while uscita=false do 
  69. 	                      begin
  70. 	                     	altezzainiziale:=mediana-d-(idmediana-1); (*vario di +-1 il valore della mediana finchè trovo il costo minore*)
  71. 	                        altezzainiziale1:=mediana+d -(idmediana1-1); (*di conseguenza varia la altezza iniziale dalla quale partono i livelli*)
  72. 	                        if altezzainiziale1<0 then begin d:=d+1; continue; end;
  73. 	                        if altezzainiziale<0 then altezzainiziale:=0;
  74. 	                        if altezzainiziale1<=0 then altezzainiziale1:=0;
  75. 	                        for i:=1 to N do
  76. 	                             begin 
  77. 	                               calcolacosto:=(ricordaltezze[i] - (altezzainiziale +i-1));
  78. 	                               if calcolacosto<0 then calcolacosto:=-calcolacosto;
  79. 	                               costo:= costo + calcolacosto ;
  80. 	                               calcolacosto1:=(ricordaltezze[i] - (altezzainiziale1 +i-1));
  81. 	                               if calcolacosto1<0 then calcolacosto1:=-calcolacosto1;
  82. 	                               costo1:= costo1 + calcolacosto1 ;
  83. 	                             end;
  84.  
  85. 	                        if costo<=costo1 then begin costomin:=costo; if ricordaintervallo='s' then invariato:=true; ricordaintervallo:='s'; end;
  86. 	                        if costo1<costo then  begin costomin:=costo1; if ricordaintervallo='d' then  invariato:=true; ricordaintervallo:='d';end;
  87.  
  88. 	                        if (costomin<ricordacostomin) then ricordacostomin:=costomin
  89. 	                                                       else if ((costomin=ricordacostomin) and (invariato=true ))  then uscita:=true
  90. 	                                                       else if (costomin>ricordacostomin)  then uscita:=true;
  91.  
  92.  
  93. 	                        writeln(mediana,' ',altezzainiziale,' ',altezzainiziale1, ' ',costo,' ',costo1,' ',costomin,' ',ricordaintervallo,' ',ricordacostomin, invariato);
  94. 	                        costo:=0; costo1:=0; d:=d+1;
  95. 	                     end; 
  96. 	     writeln(ricordacostomin);          
  97. 	  end; 
  98. end.
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
50
40 19 38 25 11 48 14 27 45 27 42 29 49 43 37 49 4 23 17 30 2 22 19 15 17 41 10 30 46 13 13 36 32 2 11 46 2 27 23 47 7 17 28 6 10 15 6 14 40 25
stdout
copy 
24 0 0 990 990 990 s 990FALSE
24 0 1 990 990 990 s 990TRUE
990
https://ideone.com/GeimOK
language:
Pascal (fpc 3.0.4)
created:
11 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!