Pagini recente » Cod sursa (job #2964076) | Cod sursa (job #3349042) | Cod sursa (job #3319635) | Cod sursa (job #3300941) | Cod sursa (job #3311264)
#include <bits/stdc++.h>
#define NMAX 500001
using namespace std;
ifstream in("reguli.in");
ofstream out("reguli.out");
long long x[NMAX], a[NMAX];
int pi[NMAX]; ///pi[i] = lungimea celui mai lung prefix care este si sufix al secventei formate din primele i valori ale sirului
int main()
{
int n;
in >> n;
for(int i=0; i<n; i++)
{
in >> x[i];
if(i>0)
a[i]=x[i]-x[i-1]; ///valoarea care a fost adunata la x[i-1] pentru a obtine x[i]
}
///observam ca cel mai scurt vector cerut este cea mai scurta subsecventa a vectorului a care este periodica
///vom calcula cel mai lung prefix al vectorului a care este si sufix
int l_prefix=0;
pi[1]=l_prefix;
for(int i=2; i<n; i++)
{
while(l_prefix>0 && a[l_prefix+1]!=a[i])
{
l_prefix=pi[l_prefix];
}
if(a[l_prefix+1]==a[i])
l_prefix++;
pi[i]=l_prefix;
}
int l_min=n-1; ///lungimea minima a unui sir
while(pi[l_min]!=0)
{
l_min=l_min-pi[l_min];
}
out << l_min << "\n";
for(int i=1; i<=l_min; i++) ///afisam vectorul de lungime minima
{
out << a[i] << "\n";
}
return 0;
}