Cod sursa(job #182856)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 21 aprilie 2008 13:40:50
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <bitset>

using namespace std;

long n,i,k,urm[500005],c,r,sol;
long long x,y,d[500005];
bitset <500005>ok;

int main(){
    freopen("reguli.in","r",stdin);
    freopen("reguli.out","w",stdout);
    
    scanf("%ld",&n);
    scanf("%lld",&x);
    for (i=2;i<=n;i++){
        scanf("%lld",&y);
        d[i-1]=y-x;
        x=y;
    }
    //kmp;
    n--;
    k=0;
    urm[1]=0;
    for (i=2;i<=n;i++){
        while (k>0 && d[k+1]!=d[i])k=urm[k];
        if (d[k+1]==d[i])k++;
        urm[i]=k;
    }
    //
    k=urm[n];
    while (k){
          ok[k]=1;
          k=urm[k];
    }
    //
    for (i=1;i<=n;i++){
        c=n/i;
        r=n-c*i;
        if (urm[n-r]>0)
           if ((n-r)/(n-r-urm[n-r])==c)
              if ((n-r)%(n-r-urm[n-r])==0)
                 if (ok[r])
                    {sol=i;break;}
    }
    printf("%ld\n",sol);
    for (i=1;i<=sol;i++)
        printf("%ld\n",d[i]);

return 0;
}