Pagini recente » Cod sursa (job #120547) | Cod sursa (job #835242) | Cod sursa (job #2900085) | Cod sursa (job #2214499) | Cod sursa (job #50531)
Cod sursa(job #50531)
#include <cstdio>
#include <string>
#define FIN "reguli.in"
#define FOUT "reguli.out"
#define NMAX 500001
long long a[NMAX];
int pi[NMAX], N;
char s[32], ok[NMAX];
void read ()
{
long long l, ct, x;
scanf ("%d\n", &N);
for (int i = 1; i <= N; ++ i)
{
gets (s);
l = strlen (s);
ct = 1;
x = 0;
for (int j = l - 1; j >= 0; -- j)
{
x += (s[j] - '0') * ct;
ct *= 10;
}
a[i] = x;
a[i-1] = a[i] - a[i-1];
}
N--;
}
void prefix ()
{
int k = 0;
for (int i = 2; i <= N; ++ i)
{
while (k > 0 && a[k + 1] != a[i])
k = pi[k];
if (a[k + 1] == a[i])
++ k;
pi[i] = k;
}
}
void okeul ()
{
ok[0] = 1;
for (int i = 1; i <= N; ++ i)
if (a[i] == a[N - i + 1])
ok[i] = 1;
else
break;
}
void solve ()
{
prefix ();
okeul ();
int r, c;
for (int L = 1; L <= N; ++ L)
{
r = N % L;
c = N / L;
if (pi[N - r] > 0 && (N - r) % (N - r - pi[N - r]) == 0)
if (ok[r] == 1 && (N - r) / (N - r - pi[N - r]) == c)
{
printf ("%d\n", L);
for (int i = 1; i <= L; ++ i)
printf ("%d\n", a[i]);
break;
}
}
}
int
main ()
{
freopen (FIN, "rt", stdin);
freopen (FOUT, "wt", stdout);
read ();
solve ();
return 0;
}