Cod sursa(job #982370)

Utilizator gbi250Gabriela Moldovan gbi250 Data 9 august 2013 02:03:47
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cstdio>
#define SIZE 500001

using namespace std;
int n, i, j, pi[SIZE], pz, nr;
long long first, last, a[SIZE];
int main()
{
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);
    scanf("%d%lld", &n, &first);
    for(i=2;i<=n;++i)
    {
        scanf("%lld", &last);
        a[i-1]=last-first;
        first=last;
    }
    n--;
    j=0;
    for(i=2;i<=n;++i)
    {
        while(j>0 && a[j+1]!=a[i])
            j=pi[j];
        if(a[j+1]==a[i])
            ++j;
        pi[i]=j;
    }
    for(i=1;i<=n;++i)
        if(pi[i]>0 && pi[i]%(i-pi[i])==0)
        {
            nr=pi[i];
            pz=i;
            break;
        }
    printf("%d\n", nr);
    i=pz-nr+1;
    while(i<=pz)
    {
        printf("%lld\n", a[i]);
        ++i;
    }
    return 0;
}