Cod sursa(job #478725)

Utilizator freak93Adrian Budau freak93 Data 20 august 2010 08:06:01
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 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);

int 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];
    for(i=k+1;i<=n;++i)
        if(a[i]!=a[i-k])
        {
            k=n;
            break;
        }
    g<<k<<"\n";
    for(i=1;i<=k;++i)
        g<<a[i]<<"\n";
}