Cod sursa(job #2298574)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 8 decembrie 2018 11:30:15
Problema Reguli Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("reguli.in");
ofstream g ("reguli.out");

const int NMax = 500005;

int n;

long long v[NMax], a[NMax];

int phi[NMax];

void Construieste_Phi ()
{
    int rez = 0;
    phi[1] = 0;
    for (int i = 2; i <= n-1; i++)
    {
        while (rez > 0 && v[i] != v[rez + 1])
        {
            rez = phi[rez-1];
        }

        if (v[i] == v[rez+1]) rez++;

        phi[i] = rez;
    }
}

void solve()
{
    for (int i = 1; i <= n; i++)
    {
        f >> a[i];
    }

    for (int i = 2; i <= n; i++)
    {
        v[i-1] = a[i] - a[i-1];
    }

    Construieste_Phi();

    int Minsol = (n - 1) - phi[n-1];

    g << Minsol << '\n';

    for (int i = 1; i <= Minsol; i++)
    {
        g << v[i] << '\n';
    }
}
int main()
{
    f >> n;

    solve();

    return 0;
}