Cod sursa(job #1094852)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 29 ianuarie 2014 22:14:03
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <fstream>

using namespace std;

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

int s[500001],a[500001],pi[500001],n,k,val;

int main()
{
    fin>>n;

    fin>>a[0];

    for (int i=1; i<n; ++i)
    {
        fin>>a[i];
        s[i] = a[i] - a[i-1];
    }

    pi[1] = 0;
    k = 0;

    for (int i=2; i<n; ++i)
    {
        while (s[i] != s[k+1] && k != 0)
            k = pi[k];
        if (s[i]==s[k+1])
            ++k;
        pi[i] = k;
    }

    val = n-1-k;

    fout<<val<<"\n";

    for (int i=1; i<=val; ++i)
        fout<<s[i]<<"\n";
}