Cod sursa(job #3329510)

Utilizator bogdan1479Luca Bogdan Alexandru bogdan1479 Data 13 decembrie 2025 16:33:45
Problema Reguli Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
/// https://www.infoarena.ro/automate-finite-si-kmp
#include <fstream>
#include <cstring>

using namespace std;

const int NMAX = 1e6 + 1;

ifstream fin("reguli.in");
ofstream fout("reguli.out");

int n, a[NMAX], pi[NMAX], sol = NMAX;

void calcPrefix()
{
    int x = 0;
    pi[1] = 0;
    for(int i = 2; i <= n; ++i)
    {
        while(x > 0 && a[x + 1] != a[i])
            x = pi[x];
        if(a[x + 1] == a[i])
            ++x;
        pi[i] = x;
        if(pi[i] > 0 && i % (i - pi[i]) == 0) sol = min(sol, i - pi[i]);
    }
}

void citire()
{
    fin >> n >> a[1];
    for(int i = 2; i <= n; ++i)
    {
        fin >> a[i];
        a[i - 1] = a[i] - a[i - 1];
    }
    --n;
}

void solutie()
{
    calcPrefix();
    fout << sol << "\n";
    for(int i = 1; i <= sol; ++i) fout << a[i] << "\n";
}

int main()
{
    citire();
    solutie();
    return 0;
}