1839 - Memory006: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
277 edits
Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/1839/memory006 - 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 == Fișierul de ieșire memory0...
 
Flaviu (talk | contribs)
277 edits
No edit summary
 
(5 intermediate revisions by 2 users not shown)
Line 8: Line 8:
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.
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 ==


== 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 ==
Line 16: Line 17:
* 1 ≤ k ≤ 10.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
* 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 ==
== Exemplu 1 ==
; Intrare
; Intrare
: memory006.in
: 5 3
: 5 3
: 7 4 2 4 5
: 7 4 2 4 5
; Ieșire
; Ieșire
: Datele sunt introduse correct
: memory006.out
: 2
: 2
== Exemplu 2 ==
; Intrare
: memory006.in
: 5 15000
: 7 4 2 4 5
; Ieșire
: Datele nu corespund restricțiilor impuse.


== Rezolvare ==  
== Rezolvare ==  
Line 28: Line 41:
# 1839 - Memory006
# 1839 - Memory006


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


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


def numara_secvente(n, k, sir):
     sequences_count = 0
    # Initializeaza numarul de secvente cu produsul 2k la 0
     prod = 1
     nr_secvente = 0
 
     # Initializeaza produsul curent la 1
    produs = 1
 
    # Parcurge sirul de la stanga la dreapta
     for i in range(n):
     for i in range(n):
         # Inmulteste produsul curent cu elementul curent din sir
         prod *= arr[i]
        produs *= sir[i]
        while prod % 2 == 0:
            prod //= 2
            if prod == 2 ** k:
                sequences_count += 1


        # Cat timp produsul este mai mare decat 2k, imparte produsul la primul element din sir
    with open("memory006.out", "w") as fout:
         # si avanseaza indicele de inceput al secventei cu 1
         fout.write(str(sequences_count))
        while produs > (2 ** k):
            produs //= sir[i - nr_secvente]
            nr_secvente += 1


         # Daca produsul este egal cu 2k, incrementeaza numarul de secvente cu produsul 2k
if __name__ == "__main__":
         if produs == (2 ** k):
    with open("memory006.in", "r") as fin:
            nr_secvente += 1
         n, k = map(int, fin.readline().split())
         arr = list(map(int, fin.readline().split()))
    calculate_sequences(n, k, arr)


    return nr_secvente


def valideaza_date(n, k, sir):
    # Verifica daca n si k sunt in limitele impuse
    if not (1 <= n <= 500000 and 1 <= k <= 10000):
        return False


    # Verifica daca sirul contine n numere naturale nenule
</syntaxhighlight>
    if not all(1 <= x <= 10**18 for x in sir):
== Explicatie Rezolvare ==
        return False
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.


    return True
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.


if __name__ == '__main__':
In __main__ se face citirea din fisierul de intrare "memory006.in" si se apeleaza functia calculate_sequences.
    # Citeste datele de intrare
    n, k, sir = citeste_date_intrare()
 
    # Valideaza datele de intrare
    if not valideaza_date(n, k, sir):
        print("Date de intrare invalide")
    else:
        # Numara secventele cu produsul 2k
        nr_secvente = numara_secvente(n, k, sir)
 
        # Afiseaza numarul de secvente
        print(nr_secvente)
 
 
</syntaxhighlight>
== 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).
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

Latest revision as of 20:51, 14 May 2023

Sursa: - Memory006

Cerinţa[edit]

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[edit]

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[edit]

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[edit]

  • 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[edit]

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

Exemplu 2[edit]

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


Rezolvare[edit]

Rezolvare ver. 1[edit]

<syntaxhighlight lang="python" line>

  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)


</syntaxhighlight>

Explicatie Rezolvare[edit]

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.

Retrieved from "http://wiki.universitas.ro/index.php?title=1839_-_Memory006&oldid=6460"