Cod sursa(job #985118)

Utilizator andrettiAndretti Naiden andretti Data 16 august 2013 15:05:58
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#define maxn 500005
using namespace std;

int n,sol,lmax;
int a[maxn],p[maxn],pend[maxn];

void read()
{
    int x,y;
    scanf("%d%d",&n,&x);
    for(int i=2;i<=n;i++)
     scanf("%d",&y),a[i-1]=y-x,x=y;
    n--;
}

void solve()
{
    int i,k=0;
    p[1]=0;
    for(i=2;i<=n;i++)
    {
        while(a[k+1]!=a[i] && k) k=p[k];
        if(a[k+1]==a[i]) k++;
        p[i]=k;
    }
    for(k=p[n];k!=0;k=p[k])
    {
         pend[k]=1;
         if(k<=n/2 && k>lmax) lmax=k;
    }
    for(i=1;i<=n;i++)
     if(p[i] && i%(i-p[i])==0 && n-i<=i-p[i] && pend[n-i]){
         sol=i-p[i]; return;
     }
    sol=n-lmax;
}

void print()
{
    printf("%d\n",sol);
    for(int i=1;i<=sol;i++) printf("%d\n",a[i]);
}

int main()
{
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);

    read();
    solve();
    print();

    fclose(stdin);
    fclose(stdout);
    return 0;
}