Pagini recente » Cod sursa (job #2893890) | Cod sursa (job #2090468) | Cod sursa (job #17318) | Cod sursa (job #2922364) | Cod sursa (job #783943)
Cod sursa(job #783943)
#include<cstdio>
#include<vector>
#define MAXN 500000
using namespace std;
vector<long long >dif(MAXN);
int n;
FILE *g=fopen("reguli.out","w");
int kmp(int lg)
{
vector<long long > a(lg+1),pi(lg+1),match(lg+1);
int i,k=0,max=0;
for(i=1;i<=lg;++i)
a[i]=dif[i];
pi[1]=0;
for(i=2;i<=lg;i++)
{
while(k && a[i]!=a[k+1])
k=pi[k];
if(a[i]==a[k+1])
k++;
pi[i]=k;
}
k=0;
for(i=1;i<=n;i++)
{
while(k && dif[i]!=a[k+1])
k=pi[k];
if(dif[i]==a[k+1])
++k;
match[i]=k;
max=max<k ? k :max;
}
//fprintf(g,"\n");
for(i=1;i<n;i++)
{
// fprintf(g,"%lld\n",match[i]);
if(!match[i])
return 0;
}
for(i=2;i<n;i++)
{
if(match[i]!=match[i-1]+1 && match[i-1]!=max )
return 0;
else
if(match[i-1]==max &&match[i]!=1)
return 0;
}
return 1;
}
int main ()
{
FILE * f=fopen("reguli.in","r");
//FILE *g=fopen("reguli.out","w");
fscanf(f,"%u",&n);
long long x,y;
int i;
fscanf(f,"%lld",&x);
for(i=1;i<=n;i++)
{
fscanf(f,"%lld",&y);
dif[i]=y-x;
x=y;
//fprintf(g,"%lld ",dif[i]);
}
x=0;
for(i=1;i<n && !x;i++)
if(kmp(i))
x=i;
fprintf(g,"%u\n",x);
for(i=1;i<=x;i++)
fprintf(g,"%lld\n",dif[i]);
return 0;
}