Cod sursa(job #3321749)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 11 noiembrie 2025 10:26:06
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int nmax = 5e5 + 5;

int n, v[nmax], lps[nmax];

void kmp ()
{
    int k = 0;
    for (int i = 1; i < n; i++)
    {
        while (k != 0 && v[i] != v[k])
            k = lps[k-1];
        if (v[i] == v[k])
            k++;
        lps[i] = k;
    }
}

signed main()
{
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> v[i];
    for (int i = n - 1; i >= 1; i--)
        v[i] -= v[i - 1];
    n--;
    for (int i = 0; i < n; i++)
        v[i] = v[i + 1];
    v[n] = 0;
    kmp();
    if (lps[n - 1] == 0)
    {
        fout << n << '\n';
        for (int i = 0; i < n; i++)
            fout << v[i] << '\n';
        return 0;
    }
    int rez = n - lps[n - 1];
    fout << rez << '\n';
    for (int i = 0; i < rez; i++)
        fout << v[i] << '\n';
    return 0;
}