depou

depou

Sa consideram un depou ca in figura de mai jos. Observati ca exista o linie de intrare, pe care intra n vagoane, numerotate de la 1 la n in ordinea intrarii.
Vagoanele intra in depou, urmand apoi sa iasa intr-o ordine oarecare pe linia de iesire.

Cerinta

Dat fiind numarul de vagoane sa se determine numarul de modalitati distincte de aranjare a vagoanelor pe linia de iesire.

Date de intrare

Fisierul de intrare depou.in contine o singura linie pe care este scris un numar natural n reprezentand numarul de vagoane.

Date de iesire

Fisierul de iesire depou.out va contine o singura linie pe care va fi scris un numar natural reprezentand numarul de modalitati distincte de aranjare a vagoanelor pe linia de iesire.

Restrictii

1 <= n <= 150

Exemple

depou.in

depou.out

Explicatie

3
5
Cele 5 modalitati sunt:
1 2 3
(intra vagonul 1 in depou, apoi iese; intra vagonul 2 in depou, apoi iese, intra vagonul 3 in depou si apoi iese)
1 3 2
(intra vagonul 1 in depou, apoi iese; intra vagonul 2 in depou, intra vagonul 3 in depou, iese vagonul 3, apoi iese vagonul 2)
2 1 3
(intra vagonul 1 in depou; intra vagonul 2 in depou, iese vagonul 2, iese vagonul 1, intra vagonul 3 in depou, apoi iese vagonul 3)
2 3 1
(intra vagonul 1 in depou; intra vagonul 2 in depou, apoi iese vagonul 2, intra vagonul 3 in depou, iese vagonul 3, apoi iese vagonul 1)
3 2 1
(intra vagonul 1 in depou; intra vagonul 2 in depou, intra vagonul 3 in depou, apoi iese vagonul 1, iese vagonul 2, iese vagonul 1)

Timp maxim de executie/test: 0.1 secunde

prof. Marinel Serban
Liceul de Informatica "Grigore Moisil" Iasi
marinel_serban@yahoo.com

depou.in	depou.out	Explicatie
3	5	Cele 5 modalitati sunt: 1 2 3 (intra vagonul 1 in depou, apoi iese; intra vagonul 2 in depou, apoi iese, intra vagonul 3 in depou si apoi iese) 1 3 2 (intra vagonul 1 in depou, apoi iese; intra vagonul 2 in depou, intra vagonul 3 in depou, iese vagonul 3, apoi iese vagonul 2) 2 1 3 (intra vagonul 1 in depou; intra vagonul 2 in depou, iese vagonul 2, iese vagonul 1, intra vagonul 3 in depou, apoi iese vagonul 3) 2 3 1 (intra vagonul 1 in depou; intra vagonul 2 in depou, apoi iese vagonul 2, intra vagonul 3 in depou, iese vagonul 3, apoi iese vagonul 1) 3 2 1 (intra vagonul 1 in depou; intra vagonul 2 in depou, intra vagonul 3 in depou, apoi iese vagonul 1, iese vagonul 2, iese vagonul 1)