Cod sursa(job #66140)

Utilizator sealTudose Vlad seal Data 15 iunie 2007 23:12:43
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<stdio.h>
#define Nm 500000
int Pi[Nm],n;
long long A[Nm];

void read()
{
    int i;

    freopen("reguli.in","r",stdin);
    scanf("%d",&n);
    for(i=0;i<n;++i)
	scanf("%lld",A+i);
}

int match(int k)
{
    int i;

    for(i=k<<1;i<n;i+=k)
	if(Pi[i]!=i-k)
	    return 0;
    if(Pi[n-1]!=n-k-1)
	return 0;
    return 1;
}

int solve()
{
    int i,k;

    k=Pi[1]=0;
    for(i=2;i<n;++i)
    {
	while(k && A[k+1]-A[k]!=A[i]-A[i-1])
	    k=Pi[k];
	if(A[k+1]-A[k]==A[i]-A[i-1])
	    ++k;
	Pi[i]=k;
    }

    for(i=1;i<n;++i)
	if(match(i))
	    return i;
}

void write(int k)
{
    int i;

    freopen("reguli.out","w",stdout);
    printf("%d\n",k);
    for(i=1;i<=k;++i)
	printf("%lld\n",A[i]-A[i-1]);
}

int main()
{
    read();
    write(solve());
    return 0;
}