Pagini recente » Cod sursa (job #160010) | Cod sursa (job #3290501) | Cod sursa (job #2085782) | Cod sursa (job #3207199) | Cod sursa (job #196748)
Cod sursa(job #196748)
#include <cstring>
#include <cstdio>
#define MAX_N 500001
int Dif[MAX_N],N,K[MAX_N];
void load()
{
scanf("%d",&N);
int actual,precedent;
scanf("%d",&precedent);
for (int i = 1 ; i < N ; i++)
{
scanf("%d",&actual);
Dif[i] = actual - precedent;
precedent = actual;
}
N--;
}
void prefix()
{
int i, q = 0;
for (i = 2, K[1] = 0 ; i <= N; i++)
{
while(q && Dif[q+1] != Dif[i])
q = K[q];
if (Dif[q+1] == Dif[i])
++q;
K[i] = q;
}
}
void solve()
{
int iMinLength = N;
//try all lengths
for (int L = N - 1 ; L > 0 ;L--)
{
int C = N / L;
int R = N % L;
int length = N - R - K[N-R];
if ( (K[N-R] > 0) && (L == length) && ( N - R)%L == 0 && K[N] == (K[N-R] + R))
iMinLength = L;
}
printf("%d\n",iMinLength);
for (int i = 1 ; i <= iMinLength;i++)
printf("%d\n",Dif[i]);
}
int main(int argc, char *argv[])
{
freopen("reguli.in","r",stdin);
freopen("reguli.out","w",stdout);
load();
prefix();
solve();
return 0;
}