Cod sursa(job #481207)

Utilizator APOCALYPTODragos APOCALYPTO Data 30 august 2010 21:09:24
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
using namespace std;
#include<iostream>
#include<fstream>
ofstream fout("reguli.out");
int pi[500005],a[500005],N,ok[500005];
void solve()
{
 int i,k=0,L;
 pi[1]=0;
N--;
 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;



     //cout<<pi[i]<<" ";
 }
 ok[0]=1;
 for(i=1;i<=N;i++)
  if(a[i]==a[N-i+1]&&ok[i-1]==1)
   ok[i]=1;
  //cout<<" \n";
  int r,c;
  for(L=1;L<=N;L++)
  {

  r=N%L;c=N/L;
    if( ((N-r)%(N-r-pi[N-r])==0)
       && ok[r]
       &&pi[N-r]>0
       && ((N-r)/(N-r-pi[N-r])==c))
     {
         fout<<L<<"\n";
         break;
     }
  }
     for(i=1;i<=L;i++)
     fout<<a[i]<<"\n";
     //cout<<"\ok";
}

void cit()
{int i,x,y;
    ifstream fin("reguli.in");
    fin>>N;
    fin>>x;
    for(i=1;i<=N-1;i++)
    {
        fin>>y;
        a[i]=y-x;
        x=y;
        //cout<<a[i]<<" ";

    }
    fin.close();
}

int main()
{
    cit();
    //cout<<"\n";
    solve();
    fout.close();
    return 0;
}