Cod sursa(job #2298508)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 8 decembrie 2018 11:14:20
Problema Reguli Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 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; 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 = INT_MAX;

    for (int i = 1; i <= n; i++)
    {
        if (phi[i] != 0 && i - phi[i] != 0 && i % (i - phi[i]) == 0)
        {
            Minsol = min(Minsol, i - phi[i]);
        }
    }

    if (Minsol == INT_MAX)
    {
        Minsol = n - 1;
    }

    g << Minsol << '\n';

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

    solve();

    return 0;
}