Selezioni nazionali IOI 2002
Bianco e nero (BNERO, D=3)
Il problema
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);
- 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 );
Punteggio
Su ciascun file di test, al vostro programma verrà assegnato un punteggio
compreso fra 0 e P (dove P è il massimo punteggio
ottenibile). Il punteggio che viene assegnato è calcolato come segue:
- se il vostro programma emette un file di output non
corretto, oppure se supera i limiti di tempo di esecuzione
imposti, riceverà zero punti;
- se il vostro programma non riordina correttamente la
collana (cioè, se alla fine le perline dello stesso colore
non compaiono consecutivamente), riceverà zero punti;
- sia x il numero di operazioni effettuate
dal vostro programma (cioè il numero di righe del file di
output) e sia m il numero ottimale di operazioni
(cioè il numero minimo di operazioni sufficiente per riordinare
la collana); il vostro punteggio viene calcolato come segue:
- se x=m, riceverete P
punti;
- se m<x<2m,
riceverete 2P-Px/m punti;
- se 2m<=x, riceverete zero
punti.
Esempio di input/output
L'esempio che segue è quello mostrato in Figura 1. La sequenza di
operazioni indicata nel file di output è quella indicata nelle
Figure 2 e 3.
File input.txt
9
NBNNBNBBN
File output.txt
9 2
1 5