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 maxsecvk.in 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 maxsecvk.out 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
Exemplu:
maxsecvk.in
- 9 3
- 1 2 4 1 3 6 3 2 5
maxsecvk.out
- 4 4 4 6 6 6 5
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">
- Definim o functie care preia numele fisierelor de intrare si iesire ca argumente
def max_subsequence(filename_in, filename_out):
# Deschidem fisierul de intrare pentru citire
with open(filename_in, 'r') as file:
# Citim prima linie si o impartim in doua numere, n si k
n, k = map(int, file.readline().split())
# Citim a doua linie, o impartim in numere si le stocam intr-o lista
numbers = list(map(int, file.readline().split()))
# Calculam valoarea maxima pentru fiecare subsecventa de lungime k max_values = [max(numbers[i:i+k]) for i in range(n-k+1)]
# Deschidem fisierul de iesire pentru scriere
with open(filename_out, 'w') as file:
# Scriem fiecare valoare maxima in fisier, separate prin spatii
for value in max_values:
file.write(str(value) + ' ')
- Apelam functia cu numele fisierelor de intrare si iesire
max_subsequence('maxsecvk.in', 'maxsecvk.out')
</syntaxhighlight>