Enunț

Se consideră un şir a cu n numere naturale distincte: a₁, a₂,..., a_n.
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 x_i (1<i<k) astfel încât:
x₁ < x₂ < … < x_i-1 < x_i > x_i+1 > … > x_k.

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema varf:

#include <fstream>
using namespace std;

ifstream f("varf.in");
ofstream g("varf.out");

int a[12], x[12],n,ex;

void citeste()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>a[i];
}

void scrie(int k)
{
    ex=1;
    for(int i=1;i<=k;i++)
        g<<a[x[i]]<<" ";
    g<<endl;
}

int valid(int k)
{
    int i=3;
    if(k==1) return 1;
    if (a[x[1]]>a[x[2]])return 0;
    if(k==2)return 1;
    while((a[x[i-1]]<a[x[i]])&&(i<=k))
        i++;
    if (i==k+1)return 1;
    else
        if(a[x[k-1]]>a[x[k]])return 1;
    return 0;

}

void back(int k)
{
    if(k<=n)
       for(x[k]=x[k-1]+1;x[k]<=n;x[k]++)
            if(valid(k))
            {
                if(k>=3 && a[x[k-1]]>a[x[k]])scrie(k);
                back(k+1);
            }
}

int main()
{
    citeste();
    back(1);
    if(ex==0)g<<0<<endl;
    return 0;

}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1354 varf

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1354 varf de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1354 varf