Cod sursa(job #45970)

Utilizator nemesisIchim Alexandru Eugen nemesis Data 2 aprilie 2007 10:22:30
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<stdio.h>

int n, urm[500100];
int a[500100];

void prefix()
{
  int k=0;
  for(int i=2; i<=n; ++i) {
    while(k>0 && a[k+1]!=a[i]) k=urm[k];
    if( a[k+1]==a[i]) k++;
    urm[i]= k;
  }
}

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

void solve()
{
  int l=0, ok=1, r, c;
  while(ok || l==n-1) {
    l++;
    r= (n-1)%l;
    c= (n-1)/l;

    if( urm[n-1-r]!=0 && (n-1-r)/(n-1-r-urm[n-1-r]) ==c && (n-1-r)%(n-1-r-urm[n-1-r])==0) ok=0;
    
  }

  freopen("reguli.out","w",stdout);
  printf("%d\n",l);
  for(int i=1; i<=l; ++i) printf("%d\n",a[i]);
}

int main()
{
  freopen("reguli.in","r",stdin);
  scanf("%d",&n);
  int x, y;
  scanf("%d",&y);
  for(int i=1; i<=n-1; ++i) {
    scanf("%d",&x);
    a[i]= x-y;
    y=x;
  }
   prefix();
   solve();

  //afis();
  

  return 0;
}