lacat

Lacat

== 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") ==

2976