Pagini recente » Cod sursa (job #368221) | Cod sursa (job #470137) | Cod sursa (job #2707707) | Cod sursa (job #1598300) | Cod sursa (job #163104)
Cod sursa(job #163104)
//Reguli - infoarena - Preoni 2007 Runda 2
#include <stdio.h>
#define INPUT "reguli.in"
#define OUTPUT "reguli.out"
#define NMAX 500001
int N;
int A[NMAX];
int T[NMAX];
void prefix()
{
int i, k = 0;
T[1] = 0;
for(i = 2; i <= N; ++i)
{
while((k>0) && A[i] != A[k+1])
k = T[k];
if(A[i] == A[k+1]) ++k;
T[i] = k;
}
}
int main()
{
freopen(INPUT, "r", stdin);
freopen(OUTPUT, "w", stdout);
scanf("%d", &N);
int x, y, i;
scanf("%d", &x);
for(i = 2; i <= N; ++i)
{
scanf("%d", &y);
A[i-1] = y-x;
x = y;
}
--N;
prefix();
int l;
int ok = 0;
for(l = 1; l <= N && !ok; ++l)
{
int n = N - N%l;
ok = 1;
if(!T[n]) ok = 0;
if(ok && n % (n - T[n]) != 0) ok = 0;
if(ok && n - T[n] != l) ok = 0;
int j;
for(j = n+1; j <= N && ok; ++j)
if(A[j] != A[j-n]) ok = 0;
}
printf("%d\n", --l);
for(i = 1; i <= l; ++i)
printf("%d\n", A[i]);
return 0;
}