# PBinfo #1354 – varf – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

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).

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream in("varf.in");
ofstream out("varf.out");
int nr[15], v[15], n, ex;
void afisare(int k) {
    ex = 1;
    for (int i = 1; i <= k; i++)
        out << nr[v[i]] << " ";
    out << "\n";
}
int validare(int k) {
    int i = 3;
    if (k == 1) return 1;
    if (nr[v[1]] > nr[v[2]])return 0;
    if (k == 2) return 1;
    while ((nr[v[i - 1]] < nr[v[i]]) && (i <= k)) i++;
    if (i == k + 1) return 1;
    else if (nr[v[k - 1]] > nr[v[k]])return 1;
    return 0;
}
void backtracking(int k) {
    if (k <= n)
       for (v[k] = v[k - 1] + 1; v[k] <= n; v[k]++)
            if (validare(k)) {
                if (k >= 3 && nr[v[k - 1]] > nr[v[k]])
                    afisare(k);
                backtracking(k + 1);
            }
}
int main() {
    in >> n;
    for (int i = 1; i <= n; i++)
        in >> nr[i];
    backtracking(1);
    if (ex == 0)
       out << "0";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1354)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1354/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1354/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)