Pagini recente » Cod sursa (job #1972025) | Cod sursa (job #1545091) | Rating Buleu Mihai (imihaib) | Cod sursa (job #2246409) | Cod sursa (job #273617)
Cod sursa(job #273617)
#include<stdio.h>
#define infile "reguli.in"
#define outfile "reguli.out"
#define nmax 500*1001
unsigned long long x[nmax]; //sirul cu numere
unsigned 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("%llu\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("%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;
}