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