Cod sursa(job #1046918)

Utilizator drobertDumitru Robert drobert Data 3 decembrie 2013 18:30:13
Problema Reguli Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
using namespace std;
ifstream cin( "reguli.in" );
ofstream cout( "reguli.out" );

int n, x, y, ind, t, q;
int v[ 500001 ], p[ 500001 ];
int main()
{
	int i, j;
	cin >> n;
	cin >> x;
	for ( i = 1; i <= n; i++ )
	{
		cin >> y;
		v[ i ] = y - x;
		x = y;
	}
	j = 0;
	for ( i = 2; i < n; i++ )
	{
		while ( j && v[ j + 1 ] != v[ i ] )
			j = p[ j ];
		if ( v[ j + 1 ] == v[ i ] )
			j++;
		p[ i ] = j;
	}
	q = 1;
	for ( i = 1; i < n - 1; i++ )
		if ( p[ i ] > p[ i + 1 ] )
		{
			q = 0;
			break;
		}
		else if ( p[ i ] && !ind )
			ind = i - 1;
	if ( !q || !p[ n - 1 ] ) t = n - 1;
	else t = ind;
	cout << t << '\n';
	for ( i = 1; i <= t; i++ )
		cout << v[ i ] << '\n';
}