Cod sursa(job #18421)

Utilizator stef2nStefan Istrate stef2n Data 18 februarie 2007 12:07:07
Problema Reguli Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 2, Clasele 11-12 Marime 0.83 kb
#include <stdio.h>

#define infile "reguli.in"
#define outfile "reguli.out"
#define NMAX 500005

FILE *fin,*fout;
long long a[NMAX],x[NMAX];
int n;
int pref[NMAX];

void citire()
  {
   fin=fopen(infile,"r");
   fscanf(fin,"%d",&n);
   for(int i=0;i<n;i++)
      {
       fscanf(fin,"%Ld",&x[i]);
       if(i)
         a[i]=x[i]-x[i-1];
       else
         a[i]=-1;
      }
   fclose(fin);
  }

void prefix()
  {
   int m=n-1,k,q;
   pref[1]=0;
   k=0;
   for(q=2;q<=m;q++)
      {
       while(k>0 && a[k+1]!=a[q])
            k=pref[k];
       if(a[k+1]==a[q])
         k++;
       pref[q]=k;
      }
  }

void scriere()
  {
   int sol=n-1-pref[n-1];
   fout=fopen(outfile,"w");
   fprintf(fout,"%d\n",sol);
   for(int i=1;i<=sol;i++)
      fprintf(fout,"%Ld\n",a[i]);
   fclose(fout);
  }


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