Pagini recente » Cod sursa (job #1952222) | Cod sursa (job #2879467) | Cod sursa (job #1642770) | Cod sursa (job #920486) | Cod sursa (job #197270)
Cod sursa(job #197270)
#include <stdio.h>
#include <string.h>
#define minim(a, b) ((a < b) ? a : b)
#define NMax 2000005
int M, N;
char A[NMax], ok[NMax];
int pi[NMax], pos[1024];
// pi[k] = n => cel mai lung prefix al lui M care este sufix al lui M[1:k] => n<k
//
// 1 2 3 4 5 6 7
// a a b a a b a _ _ _
// a a b a _ _ _
// pi[7] = 4
// pi[k+1] = 1+ pi[k] daca M[k+1]= M[ pi[k]+1] ;
// pi[k+1] = pi
void make_prefix(void)
{
int i = 2, q = 0;
for ( pi[1] = 0; i <= M; pi[i++] = q){
for ( ; q && A[q+1] != A[i]; q = pi[q]);
if ( A[q+1] == A[i] ) ++q;
}
}
int main(void)
{
int i, q = 0, n = 0, l = 0;
freopen("reguli.in", "r", stdin);
freopen("reguli.out", "w", stdout);
scanf("%d", &M);
for( i = 1; i< M+1; i++){
scanf("%d", &A[i]);
if(i) A[i-1] = A[i] - A[i-1];
}
memset(ok, 0, M);
make_prefix();
for(q = M-1; q!=0; ok[q] = 1, q = pi[q]);
int r,c,m, p = M;
for( l = M-1; l > 0; --l){
r = (M-1) % l;
c = (M-1) / l;
m = (M-1) - r;
if( pi[ m ] && (m % (m-pi[m])) == 0 && m/(m-pi[m]) ==c && ok[r] )
p = l;
}
printf("%d\n", p) ;
for(i = 0; i < p; i++)
printf("%d\n", A[i+1]);
return 0;
}