Fişierul intrare/ieşire:lacat.in, lacat.outSursăGrigore Moisil 2008, clasele 11-12
AutorClara Ionescu, Csaba PatcasAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test1.05 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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:

  1. Primul inel poate fi eliberat sau pus la loc oricand.
  2. 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.inlacat.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)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content