3274 - secvb: Diferență între versiuni
(Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3274/secvb 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. ==...) |
Fără descriere a modificării |
||
Linia 13: | Linia 13: | ||
== Date de ieșire == | == Date de ieșire == | ||
Fișierul de ieșire secvb.out va conține un | 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 '''numărul c''', 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 26: | ||
: 8 3 7 14 10 63 1 | : 8 3 7 14 10 63 1 | ||
; Ieșire | ; Ieșire | ||
: Datele nu corespund restricțiilor impuse. | |||
: Datele sunt introduse correct. | |||
: 3 | : 3 | ||
Linia 72: | Linia 76: | ||
if bits > t: | if bits > t: | ||
break | break | ||
return cnt | return cnt == solve(n, t, x) | ||
Linia 78: | Linia 82: | ||
n, t, x = read_input() | n, t, x = read_input() | ||
result = solve(n, t, x) | result = solve(n, t, x) | ||
if validate(n, t, x): | |||
print("Datele sunt introduse corect.") | |||
else: | |||
print("Datele nu corespund restricțiilor impuse.") | |||
print(result) | print(result) | ||
Versiunea de la data 28 aprilie 2023 14:50
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 numărul c, 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
- Intrare
- 7 6
- 8 3 7 14 10 63 1
- Ieșire
- Datele nu corespund restricțiilor impuse.
- Datele sunt introduse correct.
- 3
Rezolvare
Rezolvare ver. 1
# 3274 - secvb
def read_input():
n, t = map(int, input().split())
x = list(map(int, input().split()))
return n, t, x
def count_bits(x):
cnt = 0
while x:
cnt += x & 1
x >>= 1
return cnt
def solve(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
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)
if __name__ == '__main__':
n, t, x = read_input()
result = solve(n, t, x)
if validate(n, t, x):
print("Datele sunt introduse corect.")
else:
print("Datele nu corespund restricțiilor impuse.")
print(result)
Explicatie Rezolvare
Funcția read_input citește datele de intrare și le returnează sub formă de tuplu. 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. 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.