Pagini recente » Cod sursa (job #924827) | Cod sursa (job #1103308) | Cod sursa (job #2228461) | Cod sursa (job #2571486) | Cod sursa (job #784057)
Cod sursa(job #784057)
#include<cstdio>
#include<vector>
#define pozN 500000
using namespace std;
vector<long long >dif(pozN);
int n;
FILE *g=fopen("reguli.out","w");
void prefix(int lg)
{
vector<long long > a(pozN),pi(pozN),match(pozN);
int i,k=0,poz,max=0;
bool ok=true;
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;
max=(max<k)? k :max;
}
/*fprintf(g,"\n%u ",lg);
for(i=1;i<=lg;i++)
fprintf(g,"%lld ",pi[i]);*/
for(i=1;pi[i]==0;i++)
;
poz=i-1;
for(;i<lg;i++)
if(pi[i]>pi[i+1] && pi[i]!=max && pi[i+1]!=1)
ok=false;
if(ok)
{
fprintf(g,"%u\n",poz);
for(i=1;i<=poz;i++)
fprintf(g,"%lld\n",dif[i]);
}
else
{
fprintf(g,"%u\n ",lg);
for(i=1;i<=lg;i++)
fprintf(g,"%lld\n ",dif[i]);
}
/*return 1;
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;
poz=poz<k ? k :poz;
}
//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]!=poz )
return 0;
else
if(match[i-1]==poz &&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++)
// x=(i);
prefix(n-1);
/*fprintf(g,"%u\n",x);
for(i=1;i<=x;i++)
fprintf(g,"%lld\n",dif[i]);*/
return 0;
}