== include(page="template/taskheader" task_id="lacat") ==
Poveste si cerinta...
_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.
!problema/lacat?moisil.jpg 70%!
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).
h2. 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.
h2. Date de intrare
Fisierul de intrare $lacat.in$ ...
Pe prima linie a fisierului de intrare $lacat.in$ se afla un numar natural $N$, reprezentand numarul inelelor.
h2. Date de iesire
In fisierul de iesire $lacat.out$ ...
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_$.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $2 < N ≤ 22$
h2. Exemplu
table(example). |_. lacat.in |_. lacat.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
| 5
J1
J3
S1
J2
J1
|
h3. 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$)
== include(page="template/taskfooter" task_id="lacat") ==
