Cod sursa(job #45979)

Utilizator nemesisIchim Alexandru Eugen nemesis Data 2 aprilie 2007 10:44:18
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int n, urm[500100];
int a[500100];
char aux[500000*20], *p;

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]);
}

void citire()
{
  int x, y;
  
  fread(aux, sizeof(char), 500000*20, stdin);
  p=strtok(aux, "\n");
  y=atoi(p);
  for(int i=1; i<=n-1; ++i) {
    p=strtok(0,"\n");
    x=atoi(p);
    a[i]=x-y;
    y=x;
  }

}

int main()
{
  freopen("reguli.in","r",stdin);
  scanf("%d",&n);
  citire();
/*  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;
}