Selezioni nazionali IOI 2002

Specchio (`SPEC`, `D`=3)

Il problema

Un albero è formato da una radice e da un insieme finito e ordinato (eventualmente vuoto) di figli, che sono anch'essi alberi. Ad esempio, la Figura 1 rappresenta un albero: per convenzione, la radice viene disegnata in cima (cioè al contrario rispetto agli alberi veri). Come ogni albero, lo potete descrivere dicendo quanti figli ha la radice (in questo caso, quattro) e poi descrivendo uno a uno, nell'ordine da sinistra a destra, i quattro sottoalberi. In questo modo, ad esempio, l'albero in Figura 1 sarebbe identificato dalla seguente sequenza:

4 2 0 3 0 0 1 0 0 0 0

Figura 1. Un albero.

Infatti, l'albero ha quattro figli sotto la radice, per cui il primo numero è 4. D'altra parte, 2 0 3 0 0 1 0 è la descrizione del primo figlio, mentre gli ultimi tre figli sono ciascuno descritti da 0 (dato che non hanno figli).

Supponete di guardare l'albero riflesso in uno specchio. L'ordine dei figli di ciascun nodo risulta invertito. Per esempio, l'albero di Figura 1 appare come in Figura 2.

Figura 2. L'albero di Figura 1 allo specchio.

Questo nuovo albero è descritto dalla sequenza

4 0 0 0 2 3 1 0 0 0 0

Dati in input

Il file di input, di nome input.txt, contiene una sola riga con una sequenza di interi non negativi, separati da uno spazio. La sequenza descrive correttamente un albero: quindi il primo numero è il numero di figli della radice, ed è seguito dalle descrizioni dei figli, uno dopo l'altro, da sinistra a destra.

Dati in output

Il file di output, di nome output.txt, contiene una sola riga, costituita da una sequenza di interi non negativi separati da uno o più spazi. Questa sequenza è la descrizione dell'albero dato in input visto allo specchio.

Assunzioni

il tempo limite di esecuzione è fissato in 2 secondi;
il file di input contiene al massimo 20000 interi;
nessun nodo dell'albero ha più di 100 figli;
il file di input non contiene altri caratteri oltre a quelli indicati nel testo;
il file di output non deve contenere altri caratteri oltre a quelli indicati nel testo; inoltre, il programma non deve produrre alcun altro input/output oltre a quelli indicati: deve limitarsi a leggere il file di input e a scrivere i risultati sul file di output;

i file di input/output vanno specificati senza alcuna indicazione di path, e quindi verranno aperti in C con un'istruzione tipo

			fr = fopen( "input.txt", "r" );
			fw = fopen( "output.txt", "w" );

e in Pascal con un'istruzione tipo

			assign( fr, 'input.txt' ); reset( fr );
			assign( fw, 'output.txt' ); rewrite( fw );

Esempio di input/output

File input.txt

	4 2 0 3 0 0 1 0 0 0 0

File output.txt

	4 0 0 0 2 3 1 0 0 0 0