3959 - MaxSecvK

Cerința

Se consideră un șir A de n numere întregi. Pentru fiecare subsecvență de lungimea k să se afișeze valoarea maximă.

Date de intrare

Fișierul de intrare maxsecvkin.txt conține pe prima linie două numere naturale nenule n și k, iar pe a doua linie n numere întregi separate prin spații.

Date de ieșire

Fișierul de ieșire maxsecvkout.txt va conține n–k+1 numere întregi ce reprezintă valoarea maximă a tuturor secvențelor de lungime k.

Restricții și precizări

• 1 ≤ n ≤ 100.000
• 1 ≤ k ≤ n
• -1.000.000.000 ≤ Ai ≤ -1.000.000.000
• prin secvență înțelegem elemente aflate pe poziții consecutive în șir

Exemplul 1:

maxsecvkin.txt

9 3
1 2 4 1 3 6 3 2 5

maxsecvkout.txt

Datele de intrare corespund restrictiilor impuse
4 4 4 6 6 6 5

Exemplul 2:

maxsecvkin.txt

maxsecvk

maxsecvkout.txt

Datele de intrare nu corespund restrictiilor impuse

Explicație

Se vor afișa 7 numere. Maximul secvenței 1 2 4 este 4 Maximul secvenței 2 4 1 este 4 Maximul secvenței 4 1 3 este 4 Maximul secvenței 1 3 6 este 6 Maximul secvenței 3 6 3 este 6 Maximul secvenței 6 3 2 este 6 Maximul secvenței 3 2 5 este 5

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

def validare(nr_n, nr_k, numere): # functia de validare a datelor de intrare

   if nr_n < 1 or nr_n > 100000 or nr_k < 1 or nr_k > nr_n:
       raise ValueError
   for num in numere:
       if num < -1000000000 or num > 1000000000:
           raise ValueError
   file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def max_subsequence(numere, nr_k): # functia de rezolvare

   max_values = [max(numere[i:i + nr_k]) for i in range(len(numere) - nr_k + 1)]
   for value in max_values:
       file_out.write(str(value) + ' ')

if __name__ == '__main__':

   file_in = open('maxsecvkin.txt', 'r')         # declararea fisierelor
   file_out = open('maxsecvkout.txt', 'w')       # fisierul out trebuie declarat cu optiunea "w" (write)

   try:
       n, k = map(int, file_in.readline().split())
       numbers = list(map(int, file_in.readline().split()))

       validare(n, k, numbers)                 # apelul functiei de validare
       max_subsequence(numbers, k)               # apelul functiei de rezolvare

   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>