Cod sursa(job #984090)

Utilizator stefanzzzStefan Popa stefanzzz Data 13 august 2013 15:09:16
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <fstream>
#define MAXN 500005
using namespace std;
ifstream f("reguli.in");
ofstream g("reguli.out");

int n,kmp[MAXN],x,sol;
long long v[MAXN];

int main()
{
    int i;
    f>>n;
    n--;
    for(i=0;i<=n;i++)
        f>>v[i];
    for(i=n;i>=1;i--)
        v[i]-=v[i-1];
    for(i=2;i<=n;i++){
        while(x&&v[x+1]!=v[i])
            x=kmp[x];
        if(v[x+1]==v[i])
            x++;
        kmp[i]=x;}
    sol=2;
    for(i=2;i<=n;i++)
        if(kmp[i]<=kmp[i-1])
            sol=i+1;
    g<<sol-kmp[sol]<<'\n';
    for(i=1;i<=sol-kmp[sol];i++)
        g<<v[i]<<'\n';
    f.close();
    g.close();
    return 0;
}