fork download
copy 
  1. program monuments;
  2. Uses Math;
  3. const
  4.     MAXN = 2000000;
  5. type elenco =  array[0..MAXN-1] of longint;   
  6. var
  7.     N, K, L, i  : longint;
  8.     A           : elenco;
  9.  
  10. function demolish(N, K, L: longint; var A: elenco): longint;
  11. var right, left, h, sol: Longint;
  12.     M : array [0..2*MAXN-1] of longint;
  13. begin
  14.     if N=0 then demolish:=0
  15.            else
  16.              begin 
  17.                for h := 0 to N -1 do
  18.                          begin
  19.                           M[h] := A[h];
  20.                           M[h+N] := A[h] + K;
  21.                          end;
  22.                 sol := N;
  23.                 right := 0;
  24.                 for left:=0 to N-1 do
  25.                              begin
  26.                                while M[right]-M[left] <= L do right:=right+1;
  27.                                sol := min(sol, right-left-1);
  28.                              end;
  29.                 demolish := sol;
  30.              end;   
  31. end;
  32.  
  33. Procedure scambia (var a,b: longint);
  34. var x:longint;
  35. begin
  36.    x:=a;
  37.    a:=b;
  38.    b:=x;
  39. end;  
  40. Procedure ordinamento (estremoi,estremos: dword; var v : elenco; ordinato:boolean);
  41. var inf, sup, medio:dword;
  42.     pivot :longint;
  43. begin
  44.     inf:=estremoi;
  45.     sup:=estremos;
  46.     medio:= (estremoi+estremos) div 2;
  47.     pivot:=v[medio];
  48.     repeat
  49.       if (ordinato) then
  50.          begin
  51.             while (v[inf]<pivot) do  inf:=inf+1;
  52.             while (v[sup]>pivot) do  sup:=sup-1;
  53.          end;
  54.       if inf<=sup then
  55.        begin
  56.          scambia(v[inf],v[sup]);
  57.          inf:=inf+1;
  58.          sup:=sup-1;
  59.        end;
  60.     until inf>sup;
  61.     if (estremoi<sup) then ordinamento(estremoi,sup,v,ordinato);
  62.     if (inf<estremos) then ordinamento(inf,estremos,v,ordinato);
  63. end;
  64.  
  65. begin
  66.     {
  67.     uncomment the following lines if you want to read/write from files
  68.     assign(input,  'input.txt');  reset(input);
  69.     assign(output, 'output.txt'); rewrite(output);
  70. }
  71.     readln( N, K, L);
  72.     for i:=0 to N-1 do
  73.         read(A[i]);
  74.     readln;
  75.     for i := 0 to N-1 do
  76.         if (A[i] >= K) then A[i] := A[i]-K;
  77.     ordinamento (0,N-1,A, true);
  78.     writeln(demolish(N, K, L, A));
  79.  
  80. end.
  81.  
  82.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6 8 2
8 0 1 6 15 4
stdout
copy 
0
https://ideone.com/O32Q7e
language:
Pascal (fpc 3.0.4)
created:
3 hours 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!