Cod sursa(job #1411350)

Utilizator Ionut228Ionut Calofir Ionut228 Data 31 martie 2015 17:20:06
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>

using namespace std;

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

int N, lg;
long long x, last;
long long V[500005];
int pi[500005];

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

int main()
{
    fin >> N;
    fin >> last;
    --N;
    for (int i = 1; i <= N; ++i)
    {
        fin >> x;
        V[i] = x - last;
        last = x;
    }

    prefix();
    lg = N - pi[N];

    fout << lg << '\n';
    for (int i = 1; i <= lg; ++i)
        fout << V[i] << '\n';

   fin.close();
   fout.close();
   return 0;
}