Cod sursa(job #219716)

Utilizator dragosmihaiDragos Oana dragosmihai Data 8 noiembrie 2008 10:17:43
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>

using namespace std;

long long l,n,a[500002],p[500002];

void citire();
void prefix();
void afisare();

int main()
{
    citire();
    prefix();
    afisare();
    return 0;
}

void citire()
{
   //ifstream f("reguli.in");
    //f>>n;
    freopen("reguli.in","r",stdin);
    scanf("%lld",&n);
    long long x,y;
    //f>>x;
    scanf("%lld",&x);
    for(long long i=1;i<n;i++)
    {
        //f>>y;
        scanf("%lld",&y);
        a[i]=y-x;
        x=y;
    }
   // f.close();
}

void afisare()
{
  //  ofstream g("reguli.out");
   // g<<l<<endl;
   freopen("reguli.out","w",stdout);
   printf("%lld\n",l);
    for(long long i=1;i<=l;i++)
        //g<<a[i]<<endl;
        printf("%ld\n",a[i]);
   // g.close();
}

void prefix()
{
    long long k=0;
    for(long long i=2;i<n;i++)
    {
        while(k&&a[k+1]!=a[i])
            k=p[k];
        if(a[k+1]==a[i])
            k++;
        p[i]=k;
        if(k==0)
         l=i;
        else if(k<=p[i-1])
            l=i-1;
    }
}