Cod sursa(job #857040)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 17 ianuarie 2013 10:35:48
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#define NM 500010

using namespace std;

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

int N,i,j,K;
int PI[NM];
int A[NM];
int X[NM];

int main ()
{
    f >> N >> X[1];

    for (i=2; i<=N; i++)
    {
        f >> X[i];
        A[i-1]=X[i]-X[i-1];
    }

    N--;
    for (i=2, j=0; i<=N; i++)
    {
        while (j!=0 && A[i]!=A[j+1])
            j=PI[j];

        if (A[i]==A[j+1])
            j++;

        PI[i]=j;
    }

    K=N-PI[N];

    g << K << '\n';

    for (i=1; i<=K; i++)
        g << A[i] << '\n';

    f.close();
    g.close();

    return 0;
}