Rezolvare PBinfo #1354

Enunț

Se consideră un şir a cu n numere naturale distincte: a1, a2,..., an.
Eliminând n-k numere din șirul a vom obține un subșir de lungime k al șirului a.
Definim subșir vârf de lungime k al șirului a un subșir x cu proprietatea că acesta conține un număr xi (1<i<k) astfel încât:
x1 < x2 < … < xi-1 < xi > xi+1 > … > xk.

Cerința

Să se genereze toate subşirurile vârf ale şirului a, de lungime minim 3.

Date de intrare

Fișierul de intrare varf.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale distincte separate prin câte un spațiu, reprezentând numerele din șirul a.

Date de ieșire

Fișierul de ieșire varf.out va conține pe fiecare linie câte un subșir vârf, în ordinea lexicografică a pozițiilor ocupate în șirul a de termenii subșirului. Numerele din fiecare linie vor fi separate prin câte un spațiu.

Restricții și precizări

• 4 ≤ n ≤ 11
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 20
• subșirurile vârf vor fi scrise în fișier în ordinea lexicografică a pozițiilor ocupate în șirul a de termenii fiecărui subșir.
• dacă nu există niciun subșir vârf atunci fișierul de ieșire varf.out va conține pe prima linie valoarea 0.

Exemplu:

varf.in

4
2 1 4 3

varf.out

2 4 3 
1 4 3 

Explicație

Se pot construi doar două subșiruri vârf: (2,4,3) și (1,4,3).