Pagini recente » Cod sursa (job #2103381) | Cod sursa (job #1722204) | Cod sursa (job #3005282) | Cod sursa (job #2672114) | Cod sursa (job #1561796)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("reguli.in");
ofstream out("reguli.out");
const int MAX_N = 500000;
int n;
long long V[1 + MAX_N];
long long D[1 + MAX_N];
int PI[1 + MAX_N];
bool equalPrefSuf[1 + MAX_N];
bool testLength(int L) {
int k = n / L, r = n % L;
return(PI[n - r] > 0 &&
(n - r) % (n - r - PI[n - r]) == 0 &&
(n - r) / (n - r - PI[n - r]) == k &&
equalPrefSuf[r]);
}
int main() {
int i, l, q;
bool allTheSame;
in >> n >> V[0];
n--;
for(i = 1; i <= n; i++) {
in >> V[i];
D[i] = V[i] - V[i - 1];
}
for(i = 2, allTheSame = true; i <= n; i++) {
if(D[i] != D[1]) allTheSame = false;
}
if(allTheSame) {
out << "1\n" << V[2] - V[1] << '\n';
return 0;
}
for(i = 2, q = 0; i <= n; i++) {
while(q > 0 && D[q + 1] != D[i]) q = PI[q];
if(D[q + 1] == D[i]) q++;
PI[i] = q;
}
for(q = PI[n]; q > 0; q = PI[q]) {
equalPrefSuf[q] = true;
}
for(l = 2; l < n && testLength(l) == false; l++);
out << l << '\n';
for(i = 1; i <= l; i++) {
out << V[i] - V[i - 1] << '\n';
}
return 0;
}