Cod sursa(job #1004643)

Utilizator dariusdariusMarian Darius dariusdarius Data 3 octombrie 2013 13:18:34
Problema Reguli Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[500005];
int pi[500005];
bool periodic(int i,int n)
{
    if(!pi[i] || i%(i-pi[i])!=0)
        return false;
    int k=n-1;
    while(k!=0)
        if(pi[k]==i-pi[i])
            return true;
        else
            k=pi[k];
    return false;
}
int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    int n;long long x,y;
    scanf("%d",&n);
    scanf("%lld",&x);
    for(int i=1;i<n;i++)
    {
        scanf("%lld",&y);
        a[i]=y-x;
        x=y;
    }
    pi[1]=0;int k=0;
    for(int i=2;i<n;i++)
    {
        while(k>0 && a[k+1]!=a[i]) k=pi[k];
        if(a[k+1]==a[i]) k++;
        pi[i]=k;
    }
    int ans=n-1;
    for(int i=1;i<n;i++)
        if(periodic(i,n) && i-pi[i]<ans)
            ans=i-pi[i];
    printf("%d\n",ans);
    for(int i=1;i<=ans;i++)
        printf("%lld\n",a[i]);
    return 0;
}