Cod sursa(job #19596)
#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
unsigned int nmax=500000;
long n,p[500000];
double s[500000];
int citire()
{ double x,x1;
ifstream f("reguli.in");
f>>n>>x;
for (long i=1;i<n;i++)
{
f>>x1;
s[i]=x1-x;
x=x1;
}
n=n-1;
f.close();
return 0;
}
int prefix()
{
long q,k;
p[1]=0;
k=0;
for(q=2;q<n+1;q++)
{
while ((k > 0) && (s[k+1] != s[q]))
k=p[k];
if (s[k+1] == s[q])
++k;
p[q]=k;
}
return 0;
}
int prefixmax()
{
long i,max,lmin;
bool ok;
FILE *g;
g=fopen("reguli.out","w");
max=0;
for (i=2;i<n+1;i++)
if (( p[i] > 0 ) && ( i % (i-p[i]) == 0 )) max=i;
if (max = 0)
{ max=n;
lmin=n;
} else lmin=max-p[max];
if ((max < n ) && (n-max >= lmin))
{
lmin=n;
max=n;
}
if ((max < n) && (n-max < lmin))
{
ok=true;
for (i=max+1;i<n+1;i++)
if (s[i] != s[i-max]) { ok=false; break; }
if (ok==false)
{
max=n;
lmin=n;
}
}
fprintf(g,"%li\n",lmin);
for (i=1;i<lmin+1;i++) fprintf(g,"%li\n",s[i]);
fclose(g);
return 0;
}
int main()
{
citire();
prefix();
prefixmax();
return 0;
}