aranjare

Aranjare

== include(page="template/taskheader" task_id="aranjare") ==

Poveste si cerinta...

La festivitatea de deschidere a ONI Ploiesti, Gigel, mare amator de probleme de logica a observat ca primul rand din sala este format din $2 * N + 2$ scaune, numerotate de la stanga la dreapta de la $1$ la $2 * N + 2$. Pe acest rand s-au asezat, intr-o ordine oarecare, $N$ baieti si $N$ fete, cele doua scaune ramase libere fiind alaturate.
 
Imediat Gigel inventeaza o problema. Sa consideram ca singura mutare posibila este ca doi elevi care stau pe scaune alaturate sa se ridice si sa se aseze (in aceeasi ordine) pe cele doua locuri libere.
 
Problema consta in determinarea unei secvente de mutari dupa executarea carora toate fetele sa fie grupate in stanga randului, toti baietii sa fie grupati in dreapta, iar cele doua locuri libere sa separe fetele de baieti.
 
h2. Cerinta
 
Cunoscandu-se valoarea $N$, precum si aranjarea initiala a elevilor, sa se determine o secventa de mutari care sa conduca in final la aranjarea descrisa in enuntul problemei.

h2. Date de intrare

Fisierul de intrare $aranjare.in$ ...

Fisierul de intrare $aranjare.in$ contine pe prima linie numarul natural $N$. Linia a doua a fisierului de intrare contine un sir de $2 * N + 2$ caractere ({$N$} caractere $F$, $N$ caractere $B$ si doua caractere alaturate $S$) care reprezinta aranjarea initiala a elevilor pe rand si cele doua locuri libere. Mai exact, $F$ indica un loc ocupat de o fata, $B$ un loc ocupat de un baiat, iar $SS$ reprezinta cele doua scaune libere.

h2. Date de iesire

In fisierul de iesire $aranjare.out$ ...

Fisierul de iesire $aranjare.out$ va contine mutarile din secventa determinata, in ordine, cate o mutare pe o linie. O mutare este descrisa printr-o valoare naturala $K$ $(1 &le; K < 2 * N + 2)$ cu semnificatia "se vor muta pe scaunele libere elevii situati pe scaunele $K$ si $K + 1$".

h2. Restrictii

h2. Restrictii si precizari

* $... ≤ ... ≤ ...$

* $3 ≤ N ≤ 5000$
* Pentru datele de test exista totdeauna solutie. Solutia nu este unica.

h2. Exemplu
table(example). |_. aranjare.in |_. aranjare.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
FBSSFBFB
| 7
2
5
3
6
1
7
3
6
4

|
h3. Explicatie

...

Se vor obtine pe rand configuratiile:
 
* $FBFBFBSS$
* $FSSBFBBF$
* $FFBBSSBF$
* $FFSSBBBF$
* $FFBBBSSF$
* $SSBBBFFF$
* $FFBBBFSS$
* $FFSSBFBB$
* $FFFBBSSB$
* $FFFSSBBB$

== include(page="template/taskfooter" task_id="aranjare") ==

3075