Cod sursa(job #1202229)

Utilizator legionarulCorneliu Zelea Codreanu legionarul Data 27 iunie 2014 13:01:55
Problema Reguli Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
 # include <fstream>
 # include <cstring>
 # include <algorithm>
 # include <vector>
 
 # define dim 500005
 
 using namespace std;
 
 ifstream f("reguli.in");
 ofstream g("reguli.out");
 
 long long a[ dim ];
 int p[ dim ];
 int n;
 
 void citire()
 {
	 int i;
	 long long	curent, anterior;
	 
	 f >> n;
	 for ( i = 1 ; i <= n ; i++ )
	 {
		 f >> curent;
		 if ( i == 1 )
		 {
			 anterior = curent;
		 }
		 else
		 {
			 a[ i - 1 ] = curent - anterior;
			 anterior = curent;
		 }
	 }
	 
	 //for ( i = 1 ; i < n ; i++ )
		// g << a[ i ] << " ";
	 //g << "\n";
 }
 
 void prefix()
 {
	 int i, q = 0;
	 p[ i ] = 0;
	 for ( i = 2 ; i < n ; i++ )
	 {
		 while ( q > 0 && a[ q + 1 ] != a[ i ] )
			 q = p[ q ];
		 if ( a[ q + 1 ] == a[ i ] )
			 q++;
		 p[ i ] = q;
	 }
 }
 
 void rezolva()
 {
	 int indice = dim, i;
	 for ( i = n - 1 ; i >= 2 ; i-- )
	 {
		 if ( i % ( i - p[ i ] ) == 0 && p[ i ] != 0 )
			 indice = min( ( i - p[ i ] ), indice ); 
	 }
	 
	 g << indice << "\n";
	 for ( i = 1 ; i <= indice; i++ )
		 g << a[ i ] << "\n";
 }
 
 int main()
 {
	 citire();
	 prefix();
	 rezolva();
	 return 0;
 }