Pagini recente » Cod sursa (job #135691) | Cod sursa (job #1495224) | Cod sursa (job #1608586) | Cod sursa (job #1590108) | Cod sursa (job #274908)
Cod sursa(job #274908)
#include<stdio.h>
#define infile "reguli.in"
#define outfile "reguli.out"
#define nmax 500*1001
long long x[nmax]; //sirul cu numere
long long d[nmax]; //d[i]=x[i]-x[i-1]
int p[nmax]; //prefixul vectorului d
int n; //lungimea sirului
void citire()
{
int i;
scanf("%d\n",&n); //numarul de elemente din sir
for(i=0;i<n;i++)
scanf("%lld\n",&x[i]); //citim elementul
}
void diferente()
{
int i;
for(i=1;i<n;i++)
d[i]=x[i]-x[i-1]; //calculam vectorul pentru diferentele dintre elementele lui x pe pozitii vecine
}
void prefix()
{
int i,k=0;
p[0]=0; //cu o pozitie mai putin decat pozitia ce trebuie comparata
for(i=2;i<n;i++)
{
while(k>0&&d[i]!=d[k+1]) k=p[k]; //cat timp nu poate sa continue
if(d[i]==d[k+1]) k++; //poate sa continue
p[i]=k; //pozitia ce poate sa fie continuata
}
}
void afisare()
{
int i=n-1,j;
//for(i=n-1;p[i];i--); //cautam pozitia ultimului 0
printf("%d\n",i); //afisem lungimea minima a sirului a (cel din problema)
for(j=1;j<=i;j++)
printf("%lld\n",d[j]); //afisem sirul
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
citire();
diferente();
prefix();
afisare();
fclose(stdin);
fclose(stdout);
return 0;
}