Cod sursa(job #3163501)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 31 octombrie 2023 15:31:47
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;

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

signed main(){
    cin.tie(0);ios::sync_with_stdio(0);

    int n; fin >> n;
    vector <int> v(n);
    for(int i = 0; i < n; i++) fin >> v[i];
    for(int i = n - 1; i > 0; i--){
        v[i] = v[i] - v[i - 1];
    }
    v[0] = 0;
    v.erase(v.begin());
    n--;

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

    int lp = n - p[n - 1];
    if(p[n - 1] == 0){
        fout << n << endl;
        for(int i = 0; i < n; i++) fout << v[i] << "\n";
        cout << endl;
    }else{
        fout << lp << endl;
        for(int i = 0; i < lp; i++) fout << v[i] << "\n";
        cout << endl;
    }

    return 0;
}