Cod sursa(job #278362)

Utilizator cheery_g1rlHaller Emanuela cheery_g1rl Data 12 martie 2009 11:48:14
Problema Reguli Scor 90
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.08 kb
var p,v:array[0..500000] of int64;
    n,i,k,q,l,r,c:longint;
    o:array[1..500000] of boolean;
    ok:boolean;
procedure prefix;
    begin
      v[1]:=0; k:=0;
      for q:=2 to n do
        begin
          while (k>0)and(p[k+1]<>p[q]) do k:=v[k];
          if p[k+1]=p[q] then inc(k);
          v[q]:=k;
        end;
    end;
begin
assign(input,'reguli.in'); reset(input); assign(output,'reguli.out'); rewrite(output);
readln(n);
readln(p[0]);
for i:=1 to n-1 do begin readln(p[i]); o[i]:=false;end;
for i:=n-1 downto 1 do p[i]:=p[i]-p[i-1];
prefix;
dec(n);
ok:=false;
i:=n;
while v[i]<>0 do
  begin
    ok:=true;
    o[n-v[i]+1]:=true;
    i:=v[i];
  end;
if not ok then
   begin
     writeln(n);
     for i:=1 to n do writeln(p[i],' ');
   end
       else
   begin
ok:=false;
l:=1;
while not ok do
  begin
    r:=n mod l;
    c:=n div l;
    if (o[n-r+1])and(v[n-r]>0)and((n-r) mod (n-r-v[n-r])=0)and((n-r) div (n-r-v[n-r])=c) then ok:=true;
    inc(l);
  end;
writeln(l-1);
for i:=1 to l-1 do writeln(p[i],' ');
  end;
close(input); close(output);
end.