Cod sursa(job #3163539)

Utilizator adelina_15InfoAdelina Radoi adelina_15Info Data 31 octombrie 2023 16:45:03
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

int n;

vector<int> a;
vector<int> dif;
vector<int> pi;

int main()
{
    fin >> n;
    a.resize(n);
    dif.resize(n-1);
    pi.resize(n-1);

    for(int i = 0; i < n; i++)
    {
        fin >> a[i];
        if(i > 0)
            dif[i-1] = a[i]-a[i-1];
    }

    int k = 0;
    pi[0] = 0;
    for(int i = 1; i < n-1; i++)
    {
        while(k != 0 && dif[k] != dif[i])
            k = pi[k-1];
        if(dif[i] == dif[k])
            k++;
        pi[i] = k;
    }
    int len = n-1-pi[n-2];
    fout << len << "\n";
    for(int i = 0; i < len; i++)
        fout << dif[i] << "\n";
    return 0;
}