Cod sursa(job #982366)

Utilizator gbi250Gabriela Moldovan gbi250 Data 9 august 2013 01:44:46
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
#define SIZE 500001

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