Mai intai trebuie sa te autentifici.
Cod sursa(job #41598)
Utilizator | 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.