1354 - varf

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 varfIN.txt 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 varfOUT.txt 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. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

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.

Exemplul 1:

varfIN.txt

4
2 1 4 3

varfOUT.txt

2 4 3 
1 4 3 

Explicație

Se pot construi doar două subșiruri vârf: (2,4,3) și (1,4,3).

Exemplul 2:

varfIN.txt

3
2 1 4 3

varfOUT.txt

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>