1839 - Memory006: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
 
(Nu s-au afișat 3 versiuni intermediare efectuate de alți 2 utilizatori)
Linia 6: Linia 6:


== Date de intrare ==
== Date de intrare ==
Fișierul de intrare memory006.in conține
Fișierul de intrare memory006.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule, separate prin spații.
Dacă datele sunt introduse corect, pe ecran se va afișa:
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.


== Date de ieșire ==


== Date de ieșire ==
Dacă datele sunt introduse corect, pe ecran se va afișa:
Fișierul de ieșire memory006.out va conține pe prima linie numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k.
'''"Datele sunt introduse corect."''', apoi fișierul memory006.out va conține '''numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.


== Restricţii şi precizări ==
== Restricţii şi precizări ==
Linia 24: Linia 23:
: 7 4 2 4 5
: 7 4 2 4 5
; Ieșire
; Ieșire
: Datele sunt introduse correct
: memory006.out
: memory006.out
: Datele sunt introduse correct
: 2
: 2


Linia 31: Linia 30:
; Intrare
; Intrare
: memory006.in
: memory006.in
: 5 3 2 3
: 5 15000
: 7 4 2 4 5
: 7 4 2 4 5
; Ieșire
; Ieșire
: memory006.out
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: 1
 


== Rezolvare ==  
== Rezolvare ==  
Linia 43: Linia 41:
# 1839 - Memory006
# 1839 - Memory006


def citire_date():
def validate_input(n, k, arr):
     n = int(input())
     if not(1 <= n <= 500000 and 1 <= k <= 10000 and len(arr) == n):
     v = list(map(int, input().split()))
        print("Datele nu corespund restricțiilor impuse.")
     return n, v
        return False
     for num in arr:
        if not(1 <= num <= 10**18):
            print("Datele nu corespund restricțiilor impuse.")
            return False
    print("Datele sunt introduse corect.")
     return True


def secvmax(n, v):
def calculate_sequences(n, k, arr):
     st = dr = st_max = dr_max = suma_max = suma = 0
     if not validate_input(n, k, arr):
        return
 
    sequences_count = 0
    prod = 1
     for i in range(n):
     for i in range(n):
         if v[i] % 2 == 0:
         prod *= arr[i]
             suma += v[i]
        while prod % 2 == 0:
            dr = i
             prod //= 2
             if suma > suma_max or (suma == suma_max and dr - st > dr_max - st_max):
             if prod == 2 ** k:
                 suma_max = suma
                 sequences_count += 1
                st_max = st
                dr_max = dr
        else:
            suma = 0
            st = i + 1
    return st_max + 1, dr_max + 1


def validare(n, v):
    with open("memory006.out", "w") as fout:
    if len(v) != n:
        fout.write(str(sequences_count))
        return False
    for x in v:
        if x < 1 or x > 10**18:
            return False
    return True


if __name__ == '__main__':
if __name__ == "__main__":
     n, v = citire_date()
     with open("memory006.in", "r") as fin:
    if validare(n, v):
         n, k = map(int, fin.readline().split())
         st, dr = secvmax(n, v)
         arr = list(map(int, fin.readline().split()))
         print("Datele sunt introduse corect.")
     calculate_sequences(n, k, arr)
        print(st, dr)
     else:
        print("Datele nu corespund restricțiilor impuse.")




Linia 84: Linia 78:
</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția citeste_date_intrare citește numerele n și k de pe prima linie a fișierului de intrare, apoi citește sirul de n numere de pe a doua linie și le returnează sub formă de tuplu (n, k, sir).
Functia validate_input verifica daca datele de intrare sunt valide, in functie de restrictiile impuse. Daca toate valorile sunt valide, functia returneaza True, altfel returneaza False si afiseaza un mesaj de eroare.
Funcția numara_secvente primește numerele n, k și sirul sir și returnează numărul de secvențe ale sir care au produsul egal cu 2 ** k.
 
Pentru a număra secvențele cu produsul egal cu 2 ** k, vom parcurge sirul de la stânga la dreapta și vom menține un produs curent inițial egal cu 1 și un număr de secvențe inițial egal cu 0. La fiecare pas, vom înmulți produsul curent
Functia calculate_sequences primeste ca parametri n - numarul de elemente din sir, k - numarul dat si arr - sirul de numere date. Daca datele de intrare sunt valide, functia calculeaza numarul de secvente din sir care au produsul elementelor egal cu 2^k si il scrie in fisierul de iesire "memory006.out". Algoritmul este de a parcurge sirul si de a calcula produsul elementelor din secvente succesive, impartind la 2 pana cand produsul devine egal cu 2^k. Cand acest lucru se intampla, numarul de secvente creste cu 1.
 
In __main__ se face citirea din fisierul de intrare "memory006.in" si se apeleaza functia calculate_sequences.

Versiunea curentă din 14 mai 2023 20:51

Sursa: - Memory006


Cerinţa

Se dă un şir format din n numere naturale nenule. Să se afle numărul secvenţelor din şir care au produsul elementelor egal cu 2k, unde k este un număr natural dat.


Date de intrare

Fișierul de intrare memory006.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule, separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi fișierul memory006.out va conține numărul S, reprezentând numărul secvenţelor din şir care au produsul elementelor egal cu 2k., reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

  • 1 ≤ n ≤ 500.000
  • 1 ≤ k ≤ 10.000
  • numerele de pe a doua linie a fișierului de intrare vor fi mai mari decât 1 şi mai mici decât 10^18

Exemplu 1

Intrare
memory006.in
5 3
7 4 2 4 5
Ieșire
Datele sunt introduse correct
memory006.out
2

Exemplu 2

Intrare
memory006.in
5 15000
7 4 2 4 5
Ieșire
Datele nu corespund restricțiilor impuse.


Rezolvare

Rezolvare ver. 1

# 1839 - Memory006

def validate_input(n, k, arr):
    if not(1 <= n <= 500000 and 1 <= k <= 10000 and len(arr) == n):
        print("Datele nu corespund restricțiilor impuse.")
        return False
    for num in arr:
        if not(1 <= num <= 10**18):
            print("Datele nu corespund restricțiilor impuse.")
            return False
    print("Datele sunt introduse corect.")
    return True

def calculate_sequences(n, k, arr):
    if not validate_input(n, k, arr):
        return

    sequences_count = 0
    prod = 1
    for i in range(n):
        prod *= arr[i]
        while prod % 2 == 0:
            prod //= 2
            if prod == 2 ** k:
                sequences_count += 1

    with open("memory006.out", "w") as fout:
        fout.write(str(sequences_count))

if __name__ == "__main__":
    with open("memory006.in", "r") as fin:
        n, k = map(int, fin.readline().split())
        arr = list(map(int, fin.readline().split()))
    calculate_sequences(n, k, arr)

Explicatie Rezolvare

Functia validate_input verifica daca datele de intrare sunt valide, in functie de restrictiile impuse. Daca toate valorile sunt valide, functia returneaza True, altfel returneaza False si afiseaza un mesaj de eroare.

Functia calculate_sequences primeste ca parametri n - numarul de elemente din sir, k - numarul dat si arr - sirul de numere date. Daca datele de intrare sunt valide, functia calculeaza numarul de secvente din sir care au produsul elementelor egal cu 2^k si il scrie in fisierul de iesire "memory006.out". Algoritmul este de a parcurge sirul si de a calcula produsul elementelor din secvente succesive, impartind la 2 pana cand produsul devine egal cu 2^k. Cand acest lucru se intampla, numarul de secvente creste cu 1.

In __main__ se face citirea din fisierul de intrare "memory006.in" si se apeleaza functia calculate_sequences.