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)
