Pagini recente » Borderou de evaluare (job #2089815) | Cod sursa (job #1961870)
#include <fstream>
using namespace std;
const int MAXN = 500005;
ifstream in("reguli.in");
ofstream out("reguli.out");
long long v[MAXN];
int n;
int prefix[MAXN];
void citire()
{
in >> n;
for (int i = 1;i <= n;++i)
in >> v[i];
for (int i = 1;i < n;++i)
v[i] = v[i + 1] - v[i];
--n;
}
void creare_prefix()
{
int k = 0;
prefix[1] = 0;
for (int i = 2;i <= n;++i)
{
while(k > 0 && v[k + 1] != v[i])
k = prefix[k];
if (v[k + 1] == v[i])
++k;
prefix[i] = k;
}
}
int l;
//sufix[i] - adevarat daca sufixul de lungime i este si prefix
bool sufix[MAXN];
void calculare_sufix()
{
for (int k = prefix[n];k != 0;k = prefix[k])
sufix[k] = true;
}
bool ok()
{
int c = n / l;
int r = n % l;
if (prefix[n - r] == 0)
return false;
if ((n - r) % (n - r - prefix[n - r]) != 0)
return false;
if ((n - r) / (n - r - prefix[n - r]) != c)
return false;
if (!sufix[r])
return false;
return true;
}
void prelucrare()
{
l = 1;
while(!ok())
++l;
}
void afisare()
{
out << l << '\n';
for (int i = 1;i <= l;++i)
out << v[i] << '\n';
}
int main()
{
citire();
creare_prefix();
calculare_sufix();
prelucrare();
afisare();
return 0;
}