.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » bile3

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
bile3


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Marele savant Lotocus a inventat dispozitivul din imaginea de mai jos, care functioneaza astfel:

  • initial cele n bile, numerotate de la 1 la n, sunt asezate în zona A, într-o ordine oarecare;
  • prin apasarea butonului identificat prin litera I prima bila din zona A cade în zona B;
  • prin apasarea butonului identificat prin litera O prima bila din zona B urca în zona C.

Cerinta

Deoarece onorabilul savant spera sa-si vânda inventia unei loterii, ajutati-l scriind un program care sa indice ordinea în care trebuie apasate cele doua butoane astfel încât plecând de la o configuratie initiala a bilelor în zona A sa se obtina o anumita configuratie a lor în zona C (ceea ce va dovedi importanta extraordinara a masinariei!).

Date de intrare

Fisierul de intrare bile.in are urmatoarea structura:

  • pe prima linie valoarea numarului natural nenul n;
  • pe a doua linie n numere naturale nenule, separate prin spatii, reprezentând configuratia initiala a bilelor în zona A, specificate in ordine de la stanga la dreapta;
  • pe a treia linie n numere naturale nenule, separate prin spatii, reprezentând configuratia finala la care trebuie sa ajunga bilele în zona C, specificate in ordine de la stanga la dreapta.

Date de iesire

Prima linie a fisierului bile.out va contine o singura linie pe care va fi scris un sir format numai din literele I si O reprezentând ordinea în care trebuie apasate cele doua butoane astfel încât plecând de la configuratia initiala sa se obtina configuratia finala sau mesajul imposibil daca nu se poate realiza acest lucru.

Restrictii

  • 1 <= n <= 2000
  • Exemple

    bile.in

    bile.out

    bile.in

    bile.out

    5
    5 4 2 1 3
    2 4 1 5 3

    IIIOOIOOIO 5
    5 4 2 1 3
    1 4 2 5 3

    imposibil

    prof. Radu Boriga
    Colegiul National "Spiru Haret" Bucuresti
    Contact:r_boriga@yahoo.com

    propunător: Prof. Emanuela Cerchez
    emanuela.cerchez@gmail.com
    Probleme recomandate
    surse trimise | ajutor