Cod sursa(job #66141)

Utilizator sealTudose Vlad seal Data 16 iunie 2007 00:17:55
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#define Nm 500000
int Pi[Nm],Ok[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 solve()
{
    int i,k,c,r;

    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;
    }
    while(k)
    {
	Ok[k]=1;
	k=Pi[k];
    }
    Ok[0]=1;

    --n;
    for(i=1;i<=n;++i)
    {
	c=n/i; r=n%i;
	if(Ok[r] && (c==1 || Pi[n-r]==n-r-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;
}