Pagini recente » Cod sursa (job #121276) | Cod sursa (job #687764) | Cod sursa (job #998380) | Cod sursa (job #3130435) | Cod sursa (job #273604)
Cod sursa(job #273604)
#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("%d\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,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("%d\n",d[j]); //afisem sirul
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
citire();
diferente();
prefix();
afisare();
fclose(stdin);
fclose(stdout);
}