Oros Ioana Diana: Pagină nouă: = 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) astfel încât: x1 <...`


2024-05-18T19:11:57Z
Pagină nouă: = 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> <...
New page
= 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>
1354 - varf - Revision history
