Pagini recente » Cod sursa (job #3233038) | Cod sursa (job #2191223) | Cod sursa (job #316304) | Cod sursa (job #434793) | Cod sursa (job #2985696)
#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");
const long long LL_INF = 1ll << 62;
const long long INF = 0x3f3f3f3f;
int n;
long long v[500005];
int lps[500005];
int main() {
fin >> n;
v[0] = LL_INF;
long long num, oldNum;
fin >> num;
for (int i = 2; i <= n; i++) {
oldNum = num;
fin >> num;
v[i - 1] = num - oldNum;
}
// LPS
int len = n;
int ans = 0;
for (int i = 2; i < len; i++) {
long long currVal = v[i];
int currIdx = lps[i - 1];
while (currIdx && currVal != v[currIdx + 1]) {
currIdx = lps[currIdx];
}
if (currVal == v[currIdx + 1]) {
currIdx++;
}
lps[i] = currIdx;
int periodLen = i - lps[i];
if (lps[i] && i % periodLen == 0) {
ans = i;
}
}
ans = n - lps[n - 1] - 1;
fout << ans << '\n';
for (int i = 1; i <= ans; i++) {
fout << v[i] << '\n';
}
// int periodLen;
// if (ans) {
// int idx = len - 1;
// while (lps[idx]) {
// idx--;
// }
// periodLen = idx;
// }
// else {
// periodLen = len - 1;
// }
// fout << periodLen << '\n';
// for (int i = 1; i <= periodLen; i++) {
// fout << v[i] << '\n';
// }
}