Editing 1354 - varf

= Enunț =
Se consideră un şir <code>a</code> cu <code>n</code> numere naturale distincte: <code>a1, a2,..., an</code>.

Eliminând <code>n-k</code> numere din șirul a vom obține un subșir de lungime <code>k</code> al șirului <code>a</code>.

Definim subșir <code>vârf</code> de lungime <code>k</code> al șirului <code>a</code> un subșir <code>x</code> cu proprietatea că acesta conține un număr <code>xi</code> (<code>1<i<k</code>) astfel încât:

<code>x1</code> <code>< x2</code> <code>< … < xi-1</code> <code>< xi</code> <code>> xi+1</code> <code>> … > xk</code>.

= Cerința =
Să se genereze toate subşirurile <code>vârf</code> ale şirului <code>a</code>, de lungime minim <code>3</code>.

= Date de intrare =
Fișierul de intrare <code>varfIN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale distincte separate prin câte un spațiu, reprezentând numerele din șirul <code>a</code>.

= Date de ieșire =
Fișierul de ieșire <code>varfOUT.txt</code> va conține pe fiecare linie câte un subșir <code>vârf</code>, în ordinea lexicografică a pozițiilor ocupate în șirul <code>a</code> de termenii subșirului. Numerele din fiecare linie vor fi separate prin câte un spațiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

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

= Exemplul 1: =
<code>varfIN.txt</code>
 4
 2 1 4 3
<code>varfOUT.txt</code>
 2 4 3 
 1 4 3 

=== Explicație ===
Se pot construi doar două subșiruri <code>vârf</code>: <code>(2,4,3)</code> și <code>(1,4,3)</code>.

== Exemplul 2: ==
<code>varfIN.txt</code>
 3
 2 1 4 3
<code>varfOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def afisare(k, fout, x, b):
    for i in range(1, k + 1):
        fout.write(str(x[b[i]]) + " ")
    fout.write('\n')


def solutie(k, x, b):
    if k >= 3:
        st, dr = 1, k
        while x[b[st]] < x[b[st + 1]]:
            st += 1
        while x[b[dr]] < x[b[dr - 1]]:
            dr -= 1
        if st != dr:
            return False
        if st == 1 or dr == k or st == k or dr == 1:
            return False
    else:
        return False
    return True


def bkt(k, n, x, b, fout, ok):
    for i in range(b[k - 1] + 1, n + 1):
        b[k] = i
        if k >= 3 and solutie(k, x, b):
            afisare(k, fout, x, b)
            ok[0] = 1
        bkt(k + 1, n, x, b, fout, ok)


def main():
    with open("varfIN.txt", "r") as fin:
        n = int(fin.readline().strip())
        x = [0] + list(map(int, fin.readline().strip().split()))

    if not (4 <= n <= 11) or any(num >= 20 for num in x[1:]):
        with open("varfOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse")
        return

    b = [0] * 30
    ok = [0]
    with open("varfOUT.txt", "w") as fout:
        bkt(1, n, x, b, fout, ok)
        if ok[0] == 0:
            fout.write("0")


if __name__ == "__main__":
    main()

</syntaxhighlight>