1839 - Memory006: Diferență între versiuni

De la Universitas MediaWiki
(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...)
 
Fără descriere a modificării
Linia 6: Linia 6:


== Date de intrare ==
== 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.
Fișierul de intrare memory006.in conține
Dacă datele sunt introduse corect, pe ecran se va afișa:
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.




Linia 21: Linia 23:
: 7 4 2 4 5
: 7 4 2 4 5
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse correct
: 2
: 2


Linia 28: Linia 32:
# 1839 - Memory006
# 1839 - Memory006


def citeste_date_intrare():
def citire_date():
     # Citeste n si k
     n = int(input())
     n, k = map(int, input().split())
     v = list(map(int, input().split()))
    return n, v


    # Citeste sirul de n numere
def secvmax(n, v):
    sir = list(map(int, input().split()))
     st = dr = st_max = dr_max = suma_max = suma = 0
 
    return n, k, sir
 
def numara_secvente(n, k, sir):
     # Initializeaza numarul de secvente cu produsul 2k la 0
    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
         if v[i] % 2 == 0:
        produs *= sir[i]
            suma += v[i]
            dr = i
            if suma > suma_max or (suma == suma_max and dr - st > dr_max - st_max):
                suma_max = suma
                st_max = st
                dr_max = dr
        else:
            suma = 0
            st = i + 1
    return st_max + 1, dr_max + 1


        # Cat timp produsul este mai mare decat 2k, imparte produsul la primul element din sir
def validare(n, v):
        # si avanseaza indicele de inceput al secventei cu 1
     if len(v) != n:
        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 produs == (2 ** k):
            nr_secvente += 1
 
    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
         return False
 
     for x in v:
     # Verifica daca sirul contine n numere naturale nenule
        if x < 1 or x > 10**18:
    if not all(1 <= x <= 10**18 for x in sir):
            return False
        return False
 
     return True
     return True


if __name__ == '__main__':
if __name__ == '__main__':
    # Citeste datele de intrare
     n, v = citire_date()
     n, k, sir = citeste_date_intrare()
     if validare(n, v):
 
        st, dr = secvmax(n, v)
    # Valideaza datele de intrare
         print("Datele sunt introduse corect.")
     if not valideaza_date(n, k, sir):
        print(st, dr)
         print("Date de intrare invalide")
     else:
     else:
         # Numara secventele cu produsul 2k
         print("Datele nu corespund restricțiilor impuse.")
        nr_secvente = numara_secvente(n, k, sir)


        # Afiseaza numarul de secvente
        print(nr_secvente)




Versiunea de la data 27 aprilie 2023 18:47

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 Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul c, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".


Date de ieșire

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.

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

Intrare
5 3
7 4 2 4 5
Ieșire
Datele nu corespund restricțiilor impuse.
Datele sunt introduse correct
2

Rezolvare

Rezolvare ver. 1

# 1839 - Memory006

def citire_date():
    n = int(input())
    v = list(map(int, input().split()))
    return n, v

def secvmax(n, v):
    st = dr = st_max = dr_max = suma_max = suma = 0
    for i in range(n):
        if v[i] % 2 == 0:
            suma += v[i]
            dr = i
            if suma > suma_max or (suma == suma_max and dr - st > dr_max - st_max):
                suma_max = suma
                st_max = st
                dr_max = dr
        else:
            suma = 0
            st = i + 1
    return st_max + 1, dr_max + 1

def validare(n, v):
    if len(v) != n:
        return False
    for x in v:
        if x < 1 or x > 10**18:
            return False
    return True

if __name__ == '__main__':
    n, v = citire_date()
    if validare(n, v):
        st, dr = secvmax(n, v)
        print("Datele sunt introduse corect.")
        print(st, dr)
    else:
        print("Datele nu corespund restricțiilor impuse.")

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

Adus de la „http://wiki.universitas.ro/index.php?title=1839_-_Memory006&oldid=5066”