Cod sursa(job #2290392)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 26 noiembrie 2018 14:50:07
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>

using namespace std;
long long v[500001];
int p[500001];
void prefix (int n){
    int i,k;
    k=0;
    for (i=2;i<=n;i++){
        while (k && v[k+1]!=v[i])
            k=p[k];
        if (v[k+1]==v[i])
            k++;
        p[i]=k;
    }
}
int main()
{
    FILE *fin=fopen ("reguli.in","r");
    FILE *fout=fopen ("reguli.out","w");
    int st,l,i,n;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;i++){
        fscanf (fin,"%lld",&v[i]);
        if (i>1)
            v[i-1]=v[i]-v[i-1];
    }
    /// perioada sirului v
    n--;
    prefix (n);
    st=0;
    for (i=1;2*i<=n;i++){
        if (p[2*i]==i){
            st=1;
            l=i;
        }
    }
    if (!st){ /// nu incap 2 perioade intregi
        fprintf (fout,"%d\n",n-p[n]);
        for (i=1;i<=n-p[n];i++)
            fprintf (fout,"%lld\n",v[i]);
        return 0;
    }
    fprintf (fout,"%d\n",l);
    for (i=1;i<=l;i++)
        fprintf (fout,"%lld\n",v[i]);
    return 0;
}