Cod sursa(job #1819044)

Utilizator hungntnktpHungntnktp hungntnktp Data 30 noiembrie 2016 06:11:15
Problema Reguli Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.47 kb
USES Math;
CONST
    tfi = 'reguli.in';
    tfo = 'reguli.out';
VAR
    fi,fo                   : text;
    n                       : longint;
    a,b                     : array[0..500010] of int64;
    z                       : array[0..500010] of longint;

Procedure inp;
    Var
        i: longint;
    Begin
        Read(fi,n);
        For i:=1 to n do read(fi,b[i]);
        dec(n);
        For i:=1 to n do a[i]:=b[i+1]-b[i];
    End;

Procedure sub1;
    Var
        i,j,res: longint;
        ok: boolean;
    Begin
        For i:=1 to n do
            begin
                ok:=true;
                For j:=i+1 to n do
                    If a[j]<>a[j-i] then
                        begin
                            ok:=false;
                            break;
                        end;
                If ok then
                    begin
                        res:=i;
                        break;
                    end;
            end;
        writeln(fo,res);
        For i:=1 to res do writeln(fo,a[i]);
    End;

Procedure init;
    Var
        i,j,l,r: longint;
    Begin
        l:=1; r:=1;
        z[1]:=n;
        For i:=2 to n do
            If i>r then
                begin
                    l:=i; r:=i;
                    While (r<=n) and (a[r-l+1]=a[r]) do inc(r);
                    z[i]:=r-l;
                    dec(r);
                end
            else
                begin
                    j:=i-l+1;
                    If z[j]<r-i+1 then z[i]:=z[j]
                    else
                        begin
                            l:=i;
                            While (r<=n) and (a[r-l+1]=a[r]) do inc(r);
                            z[i]:=r-l;
                            dec(r);
                        end;
                end;
    End;

Procedure sub2;
    Var
        i,l,res: longint;
    Begin
        res:=0;
        For i:=1 to n do
            begin
                l:=n-n mod i;
                If z[i+1]=n-i then
                    begin
                        res:=i;
                        break;
                    end;
            end;
        writeln(fo,res);
        For i:=1 to res do writeln(fo,a[i]);
    End;

BEGIN
    assign(fi,tfi); reset(fi);
    assign(fo,tfo); rewrite(fo);
        inp;
        If n<=2500 then sub1
        else
            begin
                init;
                sub2;
            end;
    close(fi); close(fo);
END.