Pagini recente » Cod sursa (job #1353486) | Cod sursa (job #2539547) | Cod sursa (job #1472610) | Cod sursa (job #978653) | Cod sursa (job #150017)
Cod sursa(job #150017)
#include <iostream>
#include <cstdio>
#include <fstream>
using namespace std;
int N,
D[500000],
pi[500000];
int main(int argc, char *argv[]) {
FILE *fi = fopen("reguli.in", "r");
fscanf(fi, "%d", &N);
int last,
now;
fscanf(fi, "%d", &last);
for (int i(1); i < N; ++i) {
fscanf(fi, "%d", &now);
D[i] = now - last;
last = now;
}
fclose(fi);
/*for (int i(0); i < N; ++i)
cout << i << " ";
cout << endl;
for (int i(0); i < N; ++i)
cout << D[i] << " ";
cout << endl;*/
// calculez pi
pi[1] = 0;
int k = 0;
for (int i(2); i < N; ++i) {
while ((k > 0) && (D[k + 1] != D[i]))
k = pi[k];
if (D[k + 1] == D[i])
++k;
pi[i] = k;
}
/*for (int i(0); i < N; ++i)
cout << pi[i] << " ";
cout << endl;*/
--N;
int L;
for (L = N; L >= 1; --L) {
//cout << L << " " << pi[L] << endl;
int r = N % L,
c = N / L;
int aux = N - r;
if (pi[aux] == 0)
continue;
//cout << "pi[L] != 0" << endl;
if (aux % (aux - pi[aux]) != 0)
continue;
//cout << "restul este bun" << endl;
if (N / (aux - pi[aux]) != c)
continue;
//cout << "catule este bun" << endl;
for (int i = N - r; i <= N; ++i)
if (D[i] != D[i - N + r])
continue;
//cout << "sfarsitul se potriveste" << endl;
break;
}
//cout << L << endl;
FILE *fo = fopen("reguli.out", "w");
fprintf(fo, "%d\n", L);
for (int i(1); i <= L; ++i)
fprintf(fo, "%d\n", D[i]);
fclose(fo);
return 0;
}