Fişierul intrare/ieşire:aranjare.in, aranjare.outSursăONI 2008, clasa a 10-a
AutorMarinel SerbanAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.1 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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. 

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.

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.

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 ≤ K < 2 * N + 2) cu semnificatia "se vor muta pe scaunele libere elevii situati pe scaunele K si K + 1".

Restrictii si precizari

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

Exemplu

aranjare.inaranjare.out
3
FBSSFBFB
7
2
5
3
6
1
7
3
6
4

Explicatie

Se vor obtine pe rand configuratiile:

  • FBFBFBSS
  • FSSBFBBF
  • FFBBSSBF
  • FFSSBBBF
  • FFBBBSSF
  • SSBBBFFF
  • FFBBBFSS
  • FFSSBFBB
  • FFFBBSSB
  • FFFSSBBB
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content