Cod sursa(job #514268)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 18 decembrie 2010 11:41:26
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>

#define NMAX 500006
#define minim(a,b) (a<b ? a : b)
#define ll long long

int sol=2000000000;
ll v[NMAX];
int pi[NMAX],n;
char viz[NMAX];

int main ()
{
    int i,q=0,val;
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&v[i]);
    for(i=1;i<n;i++)
        v[i]=v[i+1]-v[i];
    n--;
    q=0;
    for(i=2;i<=n;i++)
    {
        while(q>0 && v[q+1]!=v[i])
            q=pi[q];
        if(v[q+1]==v[i])
            q++;
        pi[i]=q;
    }
    val=pi[n];
    while(val)
    {
        viz[n-val+1]=1;
        val=pi[val];
    }
    for(i=1;i<=n;i++)
        if(pi[i] && i%(i-pi[i])==0 && viz[i+1])
            sol=minim(sol,pi[i]);
    printf("%d\n",sol);
    for(i=1;i<=sol;i++)
        printf("%lld\n",v[i]);
    return 0;
}