varf

/*
Folosind o tehnica asemanatoare celei pentru
generarea combinarilor, generam
toate subsirurile x crescatoare
de indici ai sirului a,
de lungime mai mare sau egala ca 3,
care satisfac conditiile problemei.
*/
#include <fstream>

using namespace std;
ifstream f("varf.in");
ofstream g("varf.out");
int n,a[12],x[12],p,b[2005][14],m;

void comb(int n,int k)
{
    int i,ok1,ok2;
    if(k>p)
    {   //avem deja o solutie de generare combinari de indici pe care o folosim
        i=1;
        ok1=0;
        while(i<p&&a[x[i]]<a[x[i+1]]) // verificam daca ne indreptam spre varf
            ++ok1,++i;
        ok2=0;
        while(i<p&&a[x[i]]>a[x[i+1]]) // verificam daca de la varf mai avem elemente spre dreapta
            ++ok2,++i;
        if(ok1&&ok2&&i==p) // Daca e varf il memoram
        {
            b[++m][0]=p; // Retinem lungimea solutiei
            for(i=1;i<=p;++i) // Retinem indicii pentru varf
                b[m][i]=x[i];
        }
    }
    else
        for(i=x[k-1]+1;i<=n;i++)
        {
            x[k]=i;
            comb(n,k+1); //mergem la pasul urmator, completam x[k+1]
        }
}

int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
        f>>a[i];
    for(p=3;p<=n;++p)
    comb(n,1);
    if(m==0)
        g<<0;
    else
    { // Sortez lexicografic liniile matricii
        int ok,indice_maxim,k;
        for(int i=1;i<m;i++)
        {
            for(int j=i+1;j<=m;j++)
            {
                ok=0;
                indice_maxim=max(b[i][0],b[j][0]);
                for(k=1;k<=indice_maxim;++k) // Verificam daca liniile i si j sunt in ordine lexicografica
                {
                    if(b[i][k]<b[j][k])
                    {
                        ok=1;
                        break;
                    }
                    else
                        if(b[i][k]>b[j][k])
                        {
                            ok=0;
                            break;
                        }
                }
                if(!ok) // Daca liniile nu sunt in ordine lexicografica, le inversam
                    for(int k=0;k<=indice_maxim;++k)
                        swap(b[i][k],b[j][k]);
            }
        }
        for(int i=1;i<=m;++i)
        {
            for(int j=1;j<=b[i][0];++j)
                g<<a[b[i][j]]<<' ';
            g<<'\n';
        }
    }
    return 0;
}