Cod sursa(job #219720)

Utilizator mircea_infoSuciu Mircea-Gabriel mircea_info Data 8 noiembrie 2008 10:18:47
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#define MAXIMUS 500001

using namespace std;

long long n,poz[MAXIMUS],dif[MAXIMUS],ok,sir[MAXIMUS];

void pref()
{
    long long k=0;
    for(long long i=2;i<n;i++)
    {
        while (k && dif[k+1]!=dif[i])
            k=poz[k];
        if(dif[k+1]==dif[i])
            k++;
        poz[i]=k;
    }
}

long long eok(long long x)
{
    long long aux=poz[n];
    while(poz[aux]>x)
    {
        aux=poz[aux];
    }
    if(poz[aux]==x)
            return 1;
    return 0;
}

void solve()
{
    n--;
    long long r,c;
    for(long long l=1;l<=n;l++)
    {
        r=n%l;
        c=n/l;
        if(poz[n-r]>0 && ((n-r)%(n-r-poz[n-r])==0) && ((n-r)/(n-r-poz[n-r])==c) && eok(r))
        {
            printf("%d\n",l);
            for(long long i=1;i<=l;i++)
                printf("%d\n",dif[i]);
            ok=1;
            return;
        }
    }
}

long long check()
{
    for(long long i=1;i<=n;i++)
        if(poz[i])
            return 1;
    return 0;
}

int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld",&sir[i]);
        if(i>1)
            dif[i-1]=sir[i]-sir[i-1];
    }
    pref();
    if(check())
    {
        solve();
        if(ok==0)
        {
            printf("%lld\n",n);
            for(long long i=1;i<=n;i++)
                printf("%lld\n",sir[i]);
        }
    }
    else
    {
        printf("%d\n",n-1);
        for(long long i=1;i<n;i++)
            printf("%lld\n",dif[i]);
    }
    fclose(stdout);
    return 0;
}