Cod sursa(job #18755)

Utilizator andrei_infoMirestean Andrei andrei_info Data 18 februarie 2007 13:55:49
Problema Ghiozdan Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.77 kb
//infoarena reguli preoni 2007 runda 2
const nmax = 500000;
var p : array[1..nmax] of longint;
    s : array[1..nmax] of int64;
    n:longint;

procedure citire;
var i:longint;
    x,x1 : int64;
begin
assign(input,'reguli.in'); reset(input);
readln(n);
readln(x);
for i:=1 to n-1 do
        begin
        readln(x1);
        s[i]:=x1-x;
        x:=x1;
        end;
n:=n-1;
closE(input);
end;

procedure citire2;
var i:longint;
begin
assign(input,'reguli.in'); reset(input);
readln(n);
for i:=1 to n do
        readln(s[i]);
close(input);
end;

procedure prefix;
var q,k:longint;
begin
p[1]:=0;
k:=0;
for q:=2 to n do
        begin
        while ( k > 0 ) and ( s[k+1] <> s[q]) do
                k:=p[k];
        if s[k+1] = s[q] then
                k:=k+1;
        p[q]:=k;
        end;
end;

procedure prefixmax;
var i,max,lmin:longint;
    ok:boolean;

begin
max:=0;
for i:=2 to n do
        if ( p[i] > 0 ) and ( i mod (i-p[i]) = 0) then
                max:=i;
if max = 0 then
        begin
        max:=n;
        lmin:=n;
        end
else
        lmin:=max-p[max];
if (max < n) and (n-max >= lmin) then
        begin
        lmin:=n;
        max:=n;
        end;
if (max < n) and (n-max < lmin) then
        begin
        ok:=true;
        for i:=max+1 to n do
                if s[i] <> s[i-max] then begin
                        ok:=false;
                        break;
                        end;
        if not ok then
                begin
                max:=n;
                lmin:=n;
                end;
        end;
writeln(lmin);
for i:=1 to lmin do
        writeln(s[i]);
end;


begin
citire;
//citire2;
prefix;
assign(output,'reguli.out'); rewrite(output);
prefixmax;
close(output);
end.