Cod sursa(job #2089909)

Utilizator FrequeAlex Iordachescu Freque Data 17 decembrie 2017 12:41:49
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int NMAX = 500000 + 5;
const int INF = 0x3f3f3f3f;

int n, len, period;
long long int minim = INF;
long long int v[NMAX], phi[NMAX];

void prefix()
{
    for (int i = 2; i <= len; ++i)
    {
        int last = phi[i - 1];
        while (last > 0 && v[i] != v[last + 1]) last = phi[last];
        if (v[i] == v[last + 1]) phi[i] = last + 1;
    }
}

void write()
{
    if (minim)
    {
        fout << minim << '\n';
        for (int i = 1; i <= minim; ++i)
            fout << v[i] << '\n';
    }
    else
    {
        fout << len << '\n';
        for (int i = 1; i <= len; ++i)
            fout << v[i] << '\n';
    }
}

void read()
{
    long long int x1, x2;
    fin >> n >> x1;

    for (int i = 2; i <= n; ++i)
    {
        fin >> x2;
        v[++len] = x2 - x1;
        x1 = x2;
    }
}

int main()
{
    read();
    prefix();

    for (int i = 1; i <= len; ++i)
        if (i % (i - phi[i]) == 0 && phi[i]) //prefixul i e periodic
            minim = min(minim, i - phi[i]);

    write();

    return 0;
}