3940 - Low Mem
Cerinţa[edit | edit source]
Se dă un șir cu n elemente, numere naturale și un număr k. Să se determine câte secvențe din șir au lungimea k și sunt formate din valori mai mici sau egale cu t, unde t este ultimul element al șirului.
Date de intrare[edit | edit source]
Fișierul de intrare lowmem.in conține pe prima linie numerele n și k, iar pe cea de-a doua linie cele n elemente ale șirului.
Date de ieșire[edit | edit source]
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", iar fișierul de ieșire lowmem.out va conține valoarea nrs, reprezentând numărul secvențelor din șir de lungime k, care sunt formate din valori mai mici sau egale cu t. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".
Restricţii şi precizări[edit | edit source]
- 1 ≤ k ≤ n ≤ 1.000.000.
- elementele șirului vor fi mai mici sau egale decât 2.000.000.000.
Exemple[edit | edit source]
Exemplul 1[edit | edit source]
- lowmen.in
- 8 3
- 1 4 3 5 7 3 4 5
- Ecran
- Datele sunt introduse corect.
- lowmen.out
- 3
Exemplul 2[edit | edit source]
- lowmem.in
- 7 3
- 2 3 4 5 6 7 7
- Ecran
- Datele sunt introduse corect.
- lowmem.out
- 5
Exemplul 3[edit | edit source]
- lowmem.in
- 1000001 3
- 2 3 4 5 6 7 7
- Ecran
- Datele nu corespund restricțiilor impuse.
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line="1">
- 3940 - Low Mem
import sys
def valideaza_datele(n: int, k: int, sir: list) -> bool:
""" Verifică dacă datele de intrare sunt valide. :param n: numărul de elemente din șir. :param k: lungimea secvenței căutate. :param sir: șirul de numere naturale. :return: True dacă datele sunt valide, False în caz contrar. """ if n < k or k < 1 or n > 1000000: return False if any(x > 2000000000 for x in sir): return False return True
def numara_secvente(n: int, k: int, sir: list) -> int:
""" Calculează numărul de secvențe din șir cu lungimea k și elemente mai mici sau egale cu ultimul element din șir. :param n: numărul de elemente din șir. :param k: lungimea secvenței căutate. :param sir: șirul de numere naturale. :return: numărul de secvențe căutate. """ ultimul_element = sir[-1] count = 0 for i in range(n-k+1): if all(sir[i+j] <= ultimul_element for j in range(k)): count += 1 return count
if __name__ == '__main__':
with open('lowmem.in', 'r') as fin: n, k = map(int, fin.readline().split()) sir = list(map(int, fin.readline().split()))
if valideaza_datele(n, k, sir): nrs = numara_secvente(n, k, sir) with open('lowmem.out', 'w', encoding='utf-8') as fout: fout.write("Datele sunt introduse corect.\n") fout.write(str(nrs)) else: with open('lowmem.out', 'w', encoding='utf-8') as fout: fout.write("Datele nu corespund restricțiilor impuse.\n") sys.exit()
</syntaxhighlight>
Explicatie[edit | edit source]
Funcția valideaza_datele(n: int, k: int, sir: list) -> bool:
Această funcție verifică dacă datele de intrare sunt valide pentru problema specifică. Are trei parametri:
n reprezintă numărul de elemente din șirul de numere primite ca intrare; k reprezintă lungimea secvenței căutate; sir reprezintă lista de numere naturale primite ca intrare. Funcția returnează True dacă datele sunt valide și False în caz contrar.
Funcția numara_secvente(n: int, k: int, sir: list) -> int:
Această funcție calculează numărul de secvențe din șirul de numere primite ca intrare cu lungimea k și cu elemente mai mici sau egale cu ultimul element din șir. Are trei parametri:
n reprezintă numărul de elemente din șirul de numere primite ca intrare; k reprezintă lungimea secvenței căutate; sir reprezintă lista de numere naturale primite ca intrare. Funcția returnează numărul de secvențe căutate.
Funcția main este funcția principală a programului și este rulată atunci când se rulează acest script Python. În interiorul funcției main, se deschide fișierul de intrare (lowmem.in) și se citește numărul de elemente din șir și lungimea secvenței căutate, apoi se citește lista de numere naturale. Apoi se verifică dacă datele de intrare sunt valide cu ajutorul funcției valideaza_datele și se calculează numărul de secvențe cu ajutorul funcției numara_secvente. Dacă datele sunt valide, se scrie mesajul "Datele sunt introduse corect." și numărul de secvențe în fișierul de ieșire (lowmem.out). În caz contrar, se scrie mesajul "Datele nu corespund restricțiilor impuse." în fișierul de ieșire.