3940 - Low Mem: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: == Cerinţa == 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 == 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 == Dacă datele su...)
 
Fără descriere a modificării
Linia 7: Linia 7:
"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.".
"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 ==
== Restricţii şi precizări ==
* 1 ⩽ '''n''' ⩽ 1.000
* 1 ≤ k ≤ n ≤ 1.000.000.
* elementele șirului vor fi '''mai mici sau egale''' decât 2.000.000.000.
* elementele șirului vor fi '''mai mici sau egale''' decât 2.000.000.000.
*
 


== Exemple ==
== Exemple ==
Linia 18: Linia 18:
; ''lowmen.out''
; ''lowmen.out''
:Datele sunt introduse corect.
:Datele sunt introduse corect.
:9 6
:3
:8 2 7
===Exemplul 2===
===Exemplul 2===
; ''lowmem.in''
; ''lowmem.in''
:5 2
:7 3
:10 9 8 7 6
:2 3 4 5 6 7 7
; ''lowmem.out''
; ''lowmem.out''
:Datele sunt introduse corect.
:Datele sunt introduse corect.
:3 4
:5
:9 10
===Exemplul 3===
===Exemplul 3===
; ''lowmem.in''
; ''lowmem.in''
: 10 12
: 1000001 3
: 1 2 3 4 5 6 7 8 9 10
:2 3 4 5 6 7 7
; ''lowmem.out''
; ''lowmem.out''
:Datele nu corespund restricțiilor impuse.
:Datele nu corespund restricțiilor impuse.
:0
<br>
<br>


Linia 41: Linia 38:
<syntaxhighlight lang="python" line="1">
<syntaxhighlight lang="python" line="1">
# 3940 - Low Mem
# 3940 - Low Mem
def validare(n, k, sir):
import sys
     if not (1 <= n <= 1000000 and 1 <= k <= n):
 
        return False
 
     if len(sir) != n:
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
         return False
     if any(x > 2000000000 for x in sir):
     if any(x > 2000000000 for x in sir):
Linia 51: Linia 56:




def rezolvare(n, k, sir):
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.
    """
     t = sir[-1]
     t = sir[-1]
     nrs = 0
     count = 0
     for i in range(n - k + 1):
     for i in range(n-k+1):
         if max(sir[i:i+k]) <= t:
         if all(sir[i+j] <= t for j in range(k)):
             nrs += 1
             count += 1
     return nrs
     return count




def main():
def main():
     try:
     with open('lowmem.in', 'r') as fin:
        with open("lowmem.in") as f:
        n, k = map(int, fin.readline().split())
            n, k = map(int, f.readline().split())
        sir = list(map(int, fin.readline().split()))
            sir = list(map(int, f.readline().split()))
    except:
        print("Datele nu corespund formatului cerut.")
        return
 
    if not validare(n, k, sir):
        print("Datele nu corespund restricțiilor impuse.")
        return
 
    nrs = rezolvare(n, k, sir)


     print(f"{nrs} {n-k+1}")
     if valideaza_datele(n, k, sir):
    with open("lowmem.out", "w") as f:
        nrs = numara_secvente(n, k, sir)
        f.write(str(nrs) + "\n")
        with open('lowmem.out', 'w', encoding='utf-8') as fout:
        f.write(" ".join(str(x) for x in sorted(sir)[-k:]) + "\n")
            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()


main()


if __name__ == "__main__":
    main()




Versiunea de la data 24 martie 2023 19:37

Cerinţa

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

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

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

  • 1 ≤ k ≤ n ≤ 1.000.000.
  • elementele șirului vor fi mai mici sau egale decât 2.000.000.000.


Exemple

Exemplul 1

lowmen.in
8 3
1 4 3 5 7 3 4 5
lowmen.out
Datele sunt introduse corect.
3

Exemplul 2

lowmem.in
7 3
2 3 4 5 6 7 7
lowmem.out
Datele sunt introduse corect.
5

Exemplul 3

lowmem.in
1000001 3
2 3 4 5 6 7 7
lowmem.out
Datele nu corespund restricțiilor impuse.



Rezolvare

# 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.
    """
    t = sir[-1]
    count = 0
    for i in range(n-k+1):
        if all(sir[i+j] <= t for j in range(k)):
            count += 1
    return count


def 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()

main()
Adus de la „http://wiki.universitas.ro/index.php?title=3940_-_Low_Mem&oldid=1575”