Cod sursa(job #2089882)

Utilizator FrequeAlex Iordachescu Freque Data 17 decembrie 2017 12:26:38
Problema Reguli Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int NMAX = 500000 + 5;

int n, len, period;
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()
{
    fout << period << '\n';
    for (int i = 1; i <= period; ++i)
        fout << v[i] << '\n';
}

void read()
{
    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
        {
            period = i - phi[i];
            break;
        }

    write();

    return 0;
}