| Fişierul intrare/ieşire: | lacat.in, lacat.out | Sursă | Grigore Moisil 2008, clasele 11-12 |
| Autor | Clara Ionescu, Csaba Patcas | Adăugată de |  Andrei Grigorean •wefgef |
| Timp execuţie pe test | 0.525 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Lacat
Lacatul dracului este o jucarie veche chinezeasca. Este format din inele de metal, montate pe cate o coada de lemn, astfel incat coada unui inel trece prin inelul urmator. Atunci cand lacatul este inchis, cozile sunt blocate intr-un suport de lemn de forma ovala.
Lacatul trebuie deschis, adica inelele trebuie desprinse din acest suport oval (trebuie date jos). Inelele sunt numerotate de la stanga la dreapta cu numere de la 1 la N. Intr-un pas se poate elibera sau pune la loc un singur inel, respectand urmatoarele reguli:
- Primul inel poate fi eliberat sau pus la loc oricand.
- Fiecare inel, avand numarul de ordine i > 1 poate fi eliberat sau pus la loc atunci si numai atunci cand inelul avand numarul de ordine i-1 se afla prins in suportul oval (este sus) si toate inele avand numarul de ordine mai mic decat i-1 sunt eliberate (sunt jos).
Lacatul este deschis daca toate inelele sunt eliberate (sunt jos).
Cerinta
Determinati numarul minim de pasi necesari pentru a deschide lacatul si precizati acesti pasi! Un pas consta in eliberarea unui singur inel, respectiv in punerea la loc a unui singur inel.
Date de intrare
Pe prima linie a fisierului de intrare lacat.in se afla un numar natural N, reprezentand numarul inelelor.
Date de iesire
Pe prima linie a fisierului de iesire lacat.out se va scrie un numar natural, reprezentand numarul minim de pasi necesari pentru a deschide lacatul. Incepand cu a doua linie, pe urmatoarele linii ale fisierului de iesire se vor descrie pasii care conduc la deschiderea lacatului:
- Corespunzator desprinderii celui de-al i-lea inel, in fisier se va scrie litera 'J', urmata de i.
- Corespunzator punerii la loc celui de-al i-lea inel, in fisier se va scrie litera 'S', urmata de i.
Restrictii
- 2 < N ≤ 22
Exemplu
| lacat.in | lacat.out |
|---|---|
| 3 | 5 J1 J3 S1 J2 J1 |
Explicatie
- Jos 1 (primul inel oricand se poate elibera)
- Jos 3 (inelul 3 se poate elibera, deoarece 1 este jos si 2 este sus)
- Sus 1 (primul inel oricand se poate pune sus; avem nevoie de el sus pentru a elibera inelul 2)
- Jos 2 (acum inelul 2 poate fi eliberat)
- Jos 1 (putem sa eliberam si inelul 1)
