| Fişierul intrare/ieşire: | aranjare.in, aranjare.out | Sursă | ONI 2008, clasa a 10-a |
| Autor | Marinel Serban | Adăugată de |  Bogdan-Cristian Tataroiu •bogdan2412 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 6144 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | aranjare.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
