Aranjare

aranjare

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

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.

Poveste si cerinta...

h2. Date de intrare

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.

Fisierul de intrare $aranjare.in$ ...

h2. Date de iesire

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$".

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

h2. Restrictii si precizari

h2. Restrictii

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

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

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

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

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

|
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