Cod sursa(job #3163553)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 31 octombrie 2023 16:59:12
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <vector>

using namespace std;
using ll = long long;

ifstream cin("reguli.in");
ofstream cout("reguli.out");

ll v[500002];
int main()
{
    int n;
    ll a, ca;
    cin >> n >> a;
    n--;

    for(int i = 0; i < n; i++)
    {
        cin >> ca;
        v[i] = ca - a;
        a = ca;
    }

    vector < int > pi(n);
    pi[0] = 0;
    int k = 0;

    for(int i = 1; i < n; i++)
    {
        while(k != 0 && v[k] != v[i])
            k = pi[k - 1];
        if(v[k] == v[i])
            k++;
        pi[i] = k;
    }
    cout << n - pi[n - 1] << '\n';
    for(int i = 0; i < n - pi[n - 1]; i++)
        cout << v[i] << '\n';
    return 0;
}
/*
abcdefg
8
8 10 14 13 15 19 18 20
   2  4 -1  2  4 -1  2

if(i % k != 0)
    x[i] = x[i - 1] + (a[i] % k);
else
    x[i] = x[i - 1] + a[k];

    avem nevoie de a[i]
*/