Pagini recente » Cod sursa (job #1380277) | Cod sursa (job #2315188) | Cod sursa (job #743354) | Cod sursa (job #967081) | Cod sursa (job #18462)
Cod sursa(job #18462)
#include <cstdio>
using namespace std;
const int NMAX = 1000001;
typedef long long ll;
ll v[NMAX];
int pi[NMAX], sh[NMAX];
int main() {
FILE *fin = fopen ("reguli.in", "r");
FILE *fout = fopen ("reguli.out", "w");
int n, i;
fscanf (fin, "%d\n%lld\n", &n, &v[0]);
for (i = 1; i < n; ++i) {
char s[30];
fgets(s, 30, fin);
int j, sigm;
ll x;
if (s[0] == '-') {
x = s[1] - '0';
j = 2;
sigm = 1;
} else {
x = s[0] - '0';
j = 1;
sigm = 0;
}
for (; s[j] >= '0' && s[j] <= '9'; ++j) {
x = x * 10 + (ll)s[j] - '0';
}
if (sigm) {
v[i] = -x;
} else {
v[i] = x;
}
}
for (i = n - 1; i > 0; --i) {
v[i] -= v[i - 1];
}/*
for (i = 1; i < n; ++i) {
printf ("%lld\n", v[i]);
}*/
int k = 0, ret = 2 * NMAX;
pi[1] = 0;
sh[1] = 1;
for (i = 2; i <= 2 * (n - 1); ++i) {
while (k > 0 && !(v[k + 1] == v[i] || i >= n - 1)) {
k = pi[k];
}
if (v[k + 1] == v[i] || i >= n - 1) {
k++;
}
pi[i] = k;
if (pi[i] == 0) {
sh[i] = i;
} else {
if (sh[i - pi[i]] <= pi[i]) {
sh[i] = sh[i - pi[i]];
} else {
sh[i] = i;
}
}
// printf ("pi = %d Sh[%d] = %d\n", pi[i], i, sh[i]);
if (i >= n - 1 && sh[i] < ret) {
ret = sh[i];
}
}
fprintf (fout, "%d\n", ret);
for (i = 1; i <= ret; ++i) {
fprintf (fout, "%lld\n", v[i]);
}
fclose(fout);
return 0;
}