Cod sursa(job #572041)

Utilizator TeodoraTanaseTeodora Tanase TeodoraTanase Data 4 aprilie 2011 23:08:50
Problema Reguli Scor 70
Compilator cpp Status done
Runda brasov_11_jr Marime 0.96 kb
#include <cstdio>

using namespace std;

const int M=500005;
long long a[M], p[M], b[M], maxim;
int n;

void citire()
{
    scanf ("%d %lld ",&n,&a[0]);
    for (int i=1; i<n; i++)
    {
        scanf ("%lld ",&a[i]);
        p[i-1]=a[i]-a[i-1];
    }
}

void kmp()
{
    int i=0, j=-1;
    b[i]=j;
    while (i<n-1)
    {
        while (j>=0 && p[i]!=p[j])
            j=b[j];
        i++;
        j++;
        b[i]=j;
        if (b[i]>maxim)
            maxim=b[i];
    }
}

void verif()
{
    int r=n%maxim, c=n/maxim;
    while (b[n-r]<=0 || (n-r)%(n-r-b[n-r])!=0 || (n-r)/(n-r-b[n-r])!=c)
    {
        maxim--;
        r=n%maxim; c=n/maxim;
    }
}

void afisare()
{
    printf ("%lld\n",maxim);
    for (int i=0; i<maxim; i++)
        printf ("%lld\n",p[i]);
}

int main()
{
    freopen ("reguli.in","r",stdin);
    freopen ("reguli.out","w",stdout);
    citire();
    kmp();
    verif();
    afisare();
    return 0;
}