Cod sursa(job #19596)

Utilizator recviemAlexandru Pana recviem Data 19 februarie 2007 19:43:50
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream.h>
#include <fstream.h>
#include <stdio.h>

unsigned int nmax=500000;
long n,p[500000];
double s[500000];

int citire()
{ double x,x1;
  ifstream f("reguli.in");
  f>>n>>x;
  for (long i=1;i<n;i++)
   {
    f>>x1;
    s[i]=x1-x;
    x=x1;
   }
  n=n-1;
  f.close();
return 0;
}

int prefix()
{
 long q,k;
 p[1]=0;
 k=0;
 for(q=2;q<n+1;q++)
  {
   while ((k > 0) && (s[k+1] != s[q]))
         k=p[k];
   if (s[k+1] == s[q])
         ++k;
   p[q]=k;
  }
 return 0;
}

int prefixmax()
{
 long i,max,lmin;
 bool ok;
 FILE *g;

 g=fopen("reguli.out","w");
 max=0;
 for (i=2;i<n+1;i++)
     if (( p[i] > 0 ) && ( i % (i-p[i]) == 0 )) max=i;
 if (max = 0)
 { max=n;
   lmin=n;
 } else lmin=max-p[max];
 if ((max < n ) && (n-max >= lmin))
 {
  lmin=n;
  max=n;
 }
 if ((max < n) && (n-max < lmin))
 {
  ok=true;
  for (i=max+1;i<n+1;i++)
   if (s[i] != s[i-max]) { ok=false; break; }
  if (ok==false)
  {
   max=n;
   lmin=n;
  }
 }
 fprintf(g,"%li\n",lmin);
 for (i=1;i<lmin+1;i++) fprintf(g,"%li\n",s[i]);
 fclose(g);
 return 0;
}

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