Cod sursa(job #18606)

Utilizator vladcyb1Vlad Berteanu vladcyb1 Data 18 februarie 2007 12:46:33
Problema Reguli Scor 70
Compilator fpc Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 1.54 kb

  const
       FIN = 'reguli.in';
       FOUT = 'reguli.out';
       NMAX = 1000000;


  var
      A : array[ 1..NMAX ] of int64;
      D, PI : array[ 1..NMAX ] of longint;
      f, g : text;
      N, i, min, k, q  : longint;
      s : string;
      x0, x1 : int64;

  procedure read_data;
   var i, cod : longint;
       s : string;
   begin
    assign( f, FIN ); reset( f );
    readln( f, N );
    readln( f, s ); val( s, x0, cod );
    for i := 2 to N do
      begin
        readln( f, s );
        val( s, x1, cod );
        A[ i - 1 ] := x1 - x0;
        x0 := x1;
      end;
   close( f );
   N := N - 1;
  end;

  function equal( x, y : longint ) : boolean;
    begin
      equal := false;
     if ( x > N ) or ( y > N ) then equal := true
        else
            if A[ x ] = A[ y ] then equal := true;
     end;

 procedure kmp;
  begin
   k := 0;
  pi[ 1 ] := 0;
  for q := 2 to 2 * n do
    begin
     while ( k > 0 ) and not( equal( k + 1 , q  ) )  do k := pi[ k ];
     if equal( k + 1 , q ) then k := k + 1;
     pi[ q ] := k;
    end;

 for  i := 1 to 2 * n do
    if pi[i] = 0 then D[i] := i
                 else D[i] := D[ i - pi[ i ] ];
 min := maxlongint;
 for i := N to 2 * N do
   if D[i] < min then min := D[ i ];
end;

 procedure save;
  begin
    assign( g, FOUT ); rewrite( g );
    writeln( g, min );
    for i  := 1 to min do
       begin
        str( A[i], s );
        writeln( g, s );
       end;
  close( g );
 end;

  begin
   read_data;
   kmp;
   save;
  end.