Cod sursa(job #481103)

Utilizator probaproba proba proba Data 30 august 2010 16:26:45
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include<fstream>

using namespace std;

const char iname[]="reguli.in";
const char oname[]="reguli.out";
const int maxn=500005;

ifstream f(iname);
ofstream g(oname);

long long a[maxn],pi[maxn],n,k,i;

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i],a[i-1]=a[i]-a[i-1];
    pi[1]=0;
    --n;
    for(i=2;i<=n;++i)
    {
        while(k&&a[k+1]!=a[i])
            k=pi[k];
        if(a[k+1]==a[i])
            ++k;
        pi[i]=k;
    }
    k=n-pi[n];
    g<<k<<"\n";
    for(i=1;i<=k;++i)
        g<<a[i]<<"\n";
}