3274 - secvb: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 27: Line 27:
: 8 3 7 14 10 63 1
: 8 3 7 14 10 63 1
; Ieșire
; Ieșire
: Datele sunt introduse correct.
: secvb.out
: secvb.out
: 3


: Datele sunt introduse correct.
: 3
== Exemplu 2 ==
== Exemplu 2 ==
; Intrare
; Intrare
Line 37: Line 37:
: 99 0 7 5 23 59 1
: 99 0 7 5 23 59 1
; Ieșire
; Ieșire
: secvb.out
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.


Line 46: Line 45:
# 3274 - secvb
# 3274 - secvb


def read_input():
def count_set_bits(num):
     n, t = map(int, input().split())
     # Funcție care numără biții de 1 în reprezentarea binară a unui număr
     x = list(map(int, input().split()))
    count = 0
     return n, t, x
     while num:
        count += num & 1
        num >>= 1
     return count




def count_bits(x):
def find_sequences(N, T, seq):
     cnt = 0
     # Funcție care găsește numărul de secvențe cu proprietatea B(i, j) = T
     while x:
    count = 0
        cnt += x & 1
     prefix_sums = [0] * (N + 1)  # Prefixe de sume pentru a putea calcula B(i, j) în O(1)
        x >>= 1
    return cnt


    # Calculăm prefixele de sume ale numărului de biți de 1 din secvență
    for i in range(1, N + 1):
        prefix_sums[i] = prefix_sums[i - 1] + count_set_bits(seq[i - 1])


def solve(n, t, x):
    # Parcurgem toate perechile (i, j) și numărăm secvențele care satisfac proprietatea
    cnt = 0
     for i in range(1, N + 1):
     for i in range(n):
         for j in range(i, N + 1):
        bits = count_bits(x[i])
             if prefix_sums[j] - prefix_sums[i - 1] == T:
        if bits == t:
                 count += 1
            cnt += 1
         for j in range(i+1, n):
             bits += count_bits(x[j])
            if bits == t:
                 cnt += 1
            if bits > t:
                break
    return cnt


    return count


def validate(n, t, x):
    cnt = 0
    for i in range(n):
        bits = count_bits(x[i])
        if bits == t:
            cnt += 1
        for j in range(i+1, n):
            bits += count_bits(x[j])
            if bits == t:
                cnt += 1
            if bits > t:
                break
    return cnt == solve(n, t, x)


def validate_input(N, T, seq):
    # Funcție care validează datele de intrare
    if not (1 <= N <= 50000):
        return False
    if not (0 <= T <= 100000):
        return False
    if not all(1 <= x <= 1000 for x in seq):
        return False
    return True


if __name__ == '__main__':
 
     n, t, x = read_input()
if __name__ == "__main__":
    result = solve(n, t, x)
     # Citirea datelor de intrare
     if validate(n, t, x):
    with open("secvb.in", "r") as file:
        N, T = map(int, file.readline().split())
        seq = list(map(int, file.readline().split()))
 
    # Validarea datelor de intrare
     if not validate_input(N, T, seq):
        print("Datele nu corespund restricțiilor impuse.")
    else:
         print("Datele sunt introduse corect.")
         print("Datele sunt introduse corect.")
    else:
        print("Datele nu corespund restricțiilor impuse.")
    print(result)


        # Rezolvarea problemei și afișarea rezultatului
        result = find_sequences(N, T, seq)
        print(result)
        # Scrierea rezultatului în fișierul de ieșire
        with open("secvb.out", "w") as file:
            file.write(str(result))




</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția read_input citește datele de intrare și le returnează sub formă de tuplu.
count_bits(numar) - Această funcție primește ca argument un număr natural numar și returnează numărul de biți de 1 din reprezentarea sa în baza 2. Pentru a realiza acest lucru, se convertește numar în reprezentarea binară utilizând funcția bin() și se numără biții de 1 în reprezentare folosind funcția count().
Funcția count_bits calculează numărul de biți de 1 din reprezentarea în baza 2 a unui număr dat.
 
Funcția solve parcurge toate subsecvențele posibile din șir și calculează B(i,j) pentru fiecare subsecvență. Dacă B(i,j) este egal cu T, se incrementează contorul. Se returnează valoarea contorului.
find_sequences(N, T, nums) - Această funcție primește trei argumente: N - numărul de elemente din șir, T - numărul dorit de biți de 1 și nums - lista de numere. Funcția parcurge toate posibilele secvențe de elemente din lista și verifică dacă suma biților de 1 din secvență este egală cu T. Dacă se găsește o astfel de secvență, se incrementează un contor pentru numărul de secvențe găsite.
Funcția validate este identică cu funcția solve.
 
In structura if __name__ == '__main__': apelăm funcția read_input pentru a obține datele de intrare, apoi apelăm funcția solve pentru a rezolva problema și afișăm rezultatul.
validate_input(N, T, nums) - Această funcție primește trei argumente: N - numărul de elemente din șir, T - numărul dorit de biți de 1 și nums - lista de numere. Funcția validează dacă datele de intrare corespund restricțiilor impuse în enunțul problemei. Verificările includ verificarea limitelor pentru N și T, precum și verificarea limitelor pentru valorile din lista nums.
 
read_input() - Această funcție este responsabilă de citirea datelor de intrare din fișierul "secvb.in". Ea returnează valorile citite pentru N, T și lista nums.
 
write_output(result) - Această funcție primește rezultatul obținut și este responsabilă de scrierea rezultatului în fișierul "secvb.out" conform formatului specificat în cerințe.
 
Blocul if __name__ == "__main__": - Acesta este blocul principal al codului și se execută doar atunci când fișierul este rulat direct (nu este importat ca modul în alt script). În interiorul acestui bloc, se apelează funcțiile de citire a datelor de intrare, validare a datelor, rezolvare a problemei și scriere a rezultatului în fișierul de ieșire. Dacă datele de intrare sunt introduse corect, se afișează mesajul "Datele sunt introduse corect." în consolă.

Revision as of 21:44, 14 May 2023

Sursa: 3274 - secvb


Pentru un număr natural x, vom nota cu B(x) numărul biților de 1 din reprezentarea lui x în baza 2. De exemplu, B(6) = 2, B(15) = 4, B(16) = 1. Fie un șir de N numere naturale x1, x2, …, xN. Pentru orice două valori i și j, cu 1 ≤ i ≤ j ≤ N, vom nota prin B(i, j) = B(xi) + B(xi+1) + ... + B(xj), adică B(i, j) este numărul tuturor biților de 1 din secvența de numere xi, xi+1, …, xj.

Cerinţa

Dat șirul x1, x2, …, xN și un număr natural T, să se determine numărul secvențelor de forma xi, xi+1, …, xj cu proprietatea că B(i,j) = T.


Date de intrare

Fișierul de intrare secvb.in conține pe prima linie numerele naturale N și T, separate printr-un spațiu. Pe linia a doua se găsesc N numere naturale x1, x2, …, xN separate prin câte un spațiu.


Date de ieșire

Fișierul de ieșire secvb.out va conține: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou prima linie numerele naturale N și T, separate printr-un spațiu. Pe linia a doua se găsesc N numere naturale x1, x2, …, xN separate prin câte un spațiu., 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 ≤ 50.000
  • 0 ≤ T ≤ 100.000
  • valorile din şir sunt numere naturale cuprinse între 1 și 1000.

Exemplu 1

Intrare
secvb.in
7 6
8 3 7 14 10 63 1
Ieșire
Datele sunt introduse correct.
secvb.out
3

Exemplu 2

Intrare
secvb.in
23 - 2 -3 41
99 0 7 5 23 59 1
Ieșire
Datele nu corespund restricțiilor impuse.


Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 3274 - secvb

def count_set_bits(num):

   # Funcție care numără biții de 1 în reprezentarea binară a unui număr
   count = 0
   while num:
       count += num & 1
       num >>= 1
   return count


def find_sequences(N, T, seq):

   # Funcție care găsește numărul de secvențe cu proprietatea B(i, j) = T
   count = 0
   prefix_sums = [0] * (N + 1)  # Prefixe de sume pentru a putea calcula B(i, j) în O(1)
   # Calculăm prefixele de sume ale numărului de biți de 1 din secvență
   for i in range(1, N + 1):
       prefix_sums[i] = prefix_sums[i - 1] + count_set_bits(seq[i - 1])
   # Parcurgem toate perechile (i, j) și numărăm secvențele care satisfac proprietatea
   for i in range(1, N + 1):
       for j in range(i, N + 1):
           if prefix_sums[j] - prefix_sums[i - 1] == T:
               count += 1
   return count


def validate_input(N, T, seq):

   # Funcție care validează datele de intrare
   if not (1 <= N <= 50000):
       return False
   if not (0 <= T <= 100000):
       return False
   if not all(1 <= x <= 1000 for x in seq):
       return False
   return True


if __name__ == "__main__":

   # Citirea datelor de intrare
   with open("secvb.in", "r") as file:
       N, T = map(int, file.readline().split())
       seq = list(map(int, file.readline().split()))
   # Validarea datelor de intrare
   if not validate_input(N, T, seq):
       print("Datele nu corespund restricțiilor impuse.")
   else:
       print("Datele sunt introduse corect.")
       # Rezolvarea problemei și afișarea rezultatului
       result = find_sequences(N, T, seq)
       print(result)
       # Scrierea rezultatului în fișierul de ieșire
       with open("secvb.out", "w") as file:
           file.write(str(result))


</syntaxhighlight>

Explicatie Rezolvare

count_bits(numar) - Această funcție primește ca argument un număr natural numar și returnează numărul de biți de 1 din reprezentarea sa în baza 2. Pentru a realiza acest lucru, se convertește numar în reprezentarea binară utilizând funcția bin() și se numără biții de 1 în reprezentare folosind funcția count().

find_sequences(N, T, nums) - Această funcție primește trei argumente: N - numărul de elemente din șir, T - numărul dorit de biți de 1 și nums - lista de numere. Funcția parcurge toate posibilele secvențe de elemente din lista și verifică dacă suma biților de 1 din secvență este egală cu T. Dacă se găsește o astfel de secvență, se incrementează un contor pentru numărul de secvențe găsite.

validate_input(N, T, nums) - Această funcție primește trei argumente: N - numărul de elemente din șir, T - numărul dorit de biți de 1 și nums - lista de numere. Funcția validează dacă datele de intrare corespund restricțiilor impuse în enunțul problemei. Verificările includ verificarea limitelor pentru N și T, precum și verificarea limitelor pentru valorile din lista nums.

read_input() - Această funcție este responsabilă de citirea datelor de intrare din fișierul "secvb.in". Ea returnează valorile citite pentru N, T și lista nums.

write_output(result) - Această funcție primește rezultatul obținut și este responsabilă de scrierea rezultatului în fișierul "secvb.out" conform formatului specificat în cerințe.

Blocul if __name__ == "__main__": - Acesta este blocul principal al codului și se execută doar atunci când fișierul este rulat direct (nu este importat ca modul în alt script). În interiorul acestui bloc, se apelează funcțiile de citire a datelor de intrare, validare a datelor, rezolvare a problemei și scriere a rezultatului în fișierul de ieșire. Dacă datele de intrare sunt introduse corect, se afișează mesajul "Datele sunt introduse corect." în consolă.