Cod sursa(job #1164411)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 2 aprilie 2014 01:15:13
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>

using namespace std;

const int NMax = 500010;

int N;
long long a[NMax];
int pi[NMax];

void Read()
{
    ifstream f("reguli.in");
    f >> N;
    for (int i = 1; i <= N; ++ i)
        f >> a[i];
    f.close();
}

void Make_Pi()
{
    int k = 0;
    pi[1] = 0;
    for (int i = 2; i < N; ++ i)
    {
        while (k > 0 && a[k + 1] != a[i])
            k = pi[k];
        if (a[k+1] == a[i])
            ++k;
        pi[i] = k;
    }
}

void Solve()
{
    for (int i = 1; i < N; ++ i)
        a[i] = a[i + 1] - a[i];
    Make_Pi();
}

void Write()
{
    ofstream g("reguli.out");
    g << N - 1 - pi[N - 1] << "\n";
    for (int i = 1, limit = N - 1 - pi[N - 1]; i <= limit; ++ i)
        g << a[i] << "\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}