Mai intai trebuie sa te autentifici.

Cod sursa(job #41598)

Utilizator andrei_infoMirestean Andrei andrei_info Data 28 martie 2007 13:26:20
Problema Reguli Scor 30
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.2 kb
//infoarena reguli preoni 2007 runda 2
const nmax = 500000;
var p : array[1..nmax] of longint;
    s : array[1..nmax] of int64;
    buf:array[1..65535] of byte;
    n:longint;
    c:char;
    f:text;


function getnn:int64;
var rez:int64;
begin
rez:=0;
while (ord(c) >=48) and (ord(c) <= 57) do
        begin
        rez:=rez*10 + ord(c) - 48;
        read(f,c);
        end;
getnn:=rez;
while (((ord(c)  < 48) or ( ord(c) > 57))) and ( ord(c) <> 26)  do
       read(f,c);
end;


procedure citire;
var i:longint;
    x,x1 : int64;
begin
assign(f,'reguli.in'); reset(f); settextbuf(f,buf);
{readln(f,n);
readln(f,x);}read(f,c);
n:=getnn; x:=getnn;
for i:=1 to n-1 do
        begin
        //readln(f,x1);
        x1:=getnn;
        s[i]:=x1-x;
        x:=x1;
        end;
n:=n-1;
closE(f);
end;

{procedure citire2;
var i:longint;
begin
assign(input,'reguli.in'); reset(input); settextbuf(
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.