Vi viene data una collana costituita da N perline bianche e nere. Ogni perlina porta impresso un numero intero da 1 a N; all’inizio, leggendo i numeri delle perline in senso orario, essi compaiono consecutivamente, cioè la perlina 1 è seguita dalla perlina 2, che è seguita dalla perlina 3 eccetera. (Naturalmente, quindi, la perlina N è seguita dalla perlina 1).
Un esempio di collana è mostrato nella Figura 1.
Figura 1.Un esempio di collana con 9 perline.
Il vostro obiettivo è di riordinare le perline in modo tale che alla fine le perline dello stesso colore compaiano consecutivamente, cioè tutte le perline bianche compaiano senza interruzioni, e così pure le perline nere.
Non è importante invece quale sia l’ordine numerico delle perline alla fine.
Per riordinare le perline avete a disposizione un solo tipo di operazione, detto taglia e cuci.
Questa operazione consiste nel tagliare un segmento della collana e nel riincollarlo nella stessa posizione ma in senso inverso.
Figura 2.La collana di Figura 1 dopo un taglia e cuci del segmento compreso fra 9 e 2.
Figura 3.La collana di Figura 2 dopo un taglia e cuci del segmento compreso fra 1 e 5.
Dati in input
Il file di input, di nome input.txt, contiene due righe.
- Sulla prima riga compare il singolo intero N.
- Sulla seconda riga compaiono esattamente N caratteri, ciascuno dei quali è una B oppure una N.
In particolare, l’i-esimo carattere indica il colore della perlina numero i (B sta per bianco mentre N sta per nero).
Dati in output
Il file di output, di nome output.txt, contiene la sequenza di operazioni taglia e cuci da effettuare per riordinare correttamente le perline.
Ciascuna riga è costituita da due numeri interi (separati da uno spazio), che sono il numero della prima e dell’ultima (in senso orario) perlina del segmento che viene tagliato e riincollato.
Assunzioni
- il tempo limite di esecuzione è fissato in 2 secondi;
- 1 <= N <= 1000;
- la collana potrebbe contenere anche perline tutte dello stesso colore (in questo caso, il file di output dovrebbe essere vuoto).
Esempio
| input.txt | output.txt |
|---|---|
| 9 NBNNBNBBN |
9 2 1 5 |
L’esempio è quello mostrato in Figura 1.
La sequenza di operazioni indicata nel file di output è quella indicata nelle Figure 2 e 3.