Sequenza per tamburello

Fase Territoriale 2010

Marco ha trovato alcune antiche sequenze in un manoscritto.
Ogni sequenza è composta da N pallini pieni o vuoti e rappresenta un brano da suonare al tamburello in N istanti consecutivi di tempo: all’i-esimo istante, il tamburello viene percosso se l’i-esimo pallino è pieno e, invece, non viene percosso se tale pallino è vuoto (1 ≤ i ≤ N).
Marco vuole capire se una data sequenza è periodica: in tal caso, vuole estrarne il periodo, ossia il più piccolo segmento iniziale che si ripete nel resto della sequenza.
In altre parole, se P è la sequenza di pallini pieni e vuoti che rappresenta il periodo, allora la sequenza in input è periodica se può essere ottenuta concatenando P per due o più volte e tale P deve essere di lunghezza minima.

Per esempio, rappresentando con 1 ogni pallino pieno e con 0 ogni pallino vuoto, la sequenza periodica 101010101010 ha 10 come periodo e la sequenza 1010010100010100101000 ha 10100101000 come periodo.
Invece, la sequenza 11011011 non è periodica.

Aiutate Marco in questo compito, in modo che possa imparare a suonare velocemente tali brani per tamburello.

Dati di input

Il file input.txt è composto da due righe.

• La prima riga contiene un intero positivo N, che indica il numero di pallini nella sequenza.
• La seconda riga contiene una sequenza di interi 0 e 1, separati da uno spazio, dove 1 rappresenta un pallino pieno e 0 un pallino vuoto.

Dati di output

Il file output.txt è composto da una sola riga contenente l’intero 2 se la sequenza in input non è periodica.
Altrimenti, se è periodica, la riga contiene la sequenza di 0 e 1, separati da uno spazio, che rappresenta il periodo P della sequenza fornita in input.

Assunzioni

• 2 ≤ N ≤ 100000.

Esempi di input/output

input.txt	output.txt
12 1 0 1 0 1 0 1 0 1 0 1 0	1 0
22 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 0	1 0 1 0 0 1 0 1 0 0 0
8 1 1 0 1 1 0 1 1	2

/*
	www.valcon.it
	OII 2010 - Fase territoriale - Sequenza per tamburello
*/

#include
#include
using namespace std;

#define NMAX 100000

int pallini[NMAX];

bool controllo(int lung, int p)
{
	for(int i=0; i < lung; i++)
		if(pallini[i] != pallini[p+i])
			return false;
	return true;
}


int main()
{
	ifstream fin ( "input.txt");
	ofstream fout("output.txt");

    int N;
	fin >> N;
	for(int i=0; i < N; i++)
		fin >> pallini[i];

    int lungMax=N/2;
    int lunghe =1;
    int volte;
    int prossima;
    while(lunghe <= lungMax)
    {
    	if(N%lunghe == 0)
    	{
    		volte   =N/lunghe;
    		prossima=1;
    		while(prossima < volte && controllo(lunghe, prossima*lunghe))
    			prossima++;
		}
		if(prossima >= volte) break;
		lunghe++;
	}
	
	if(lunghe > lungMax)
		fout << "2";
	else	
	    for(int i=0; i < lunghe; i++)
	    	fout << pallini[i] << ' ';
		
	return 0;
}