Cod sursa(job #1148438)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 20 martie 2014 19:33:30
Problema Reguli Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<fstream>
#define NMAX 500100

using namespace std;

ifstream f("reguli.in");
ofstream g("reguli.out");

long long n, per=0, a[NMAX], pi[NMAX];

void Citeste()
{
    int i, cr, pc;
    f>>n>>pc;
    for (i=1; i<n; ++i)
    {
        f>>cr;
        a[i]=cr-pc;
        pc=cr;
    }
}

void Solve()
{
    int k=0, mx=-1, i;

    pi[1]=0;

    for (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;

        if (k==0) per=i;
    }

    per=n-1;
    while (per>0 && pi[per-1]+1==pi[per] && pi[per]>1)
        per=pi[per];
}

void Scrie()
{
    int i;
    g<<per<<"\n";
    for (i=1; i<=per; ++i) g<<a[i]<<"\n";

}

int main()
{
    Citeste();

    Solve();

    Scrie();

    f.close();
    g.close();
    return 0;
}