2714 - Frecv Imp: Diferență între versiuni
De la Universitas MediaWiki
mFără descriere a modificării |
mFără descriere a modificării |
||
Linia 6: | Linia 6: | ||
Fișierul de ieșire '''frecvimp.out''' va conține pe prima linie numărul '''p''', reprezentând singura valoare din șirul dat care este putere a lui 2 și are frecvență impară. | Fișierul de ieșire '''frecvimp.out''' va conține pe prima linie numărul '''p''', reprezentând singura valoare din șirul dat care este putere a lui 2 și are frecvență impară. | ||
== Restricții și precizări == | == Restricții și precizări == | ||
* 1 les; n ⩽ 1.000.000 | * 1 ⩽ n ⩽ 1.000.000 | ||
* numerele de pe a doua linie a fișierului de intrare sunt naturale, nenule și mai mici decât <math> 9223372036854775807 </math> | * numerele de pe a doua linie a fișierului de intrare sunt naturale, nenule și mai mici decât <math> 9223372036854775807 </math> | ||
* 9223372036854775807 = 2 <sup> 63 </sup> - 1 | * <math> 9223372036854775807 </math> = 2 <sup> 63 </sup> - 1 | ||
== Exemplu == | == Exemplu == | ||
; frecvimp.in | ; frecvimp.in |
Versiunea de la data 28 octombrie 2023 12:20
Cerinţa
Se dă un șir format din n numere naturale. Toate valorile putere a lui 2 din acest șir au frecvență pară, cu o singură excepție. Determinați această valoare – putere a lui 2 cu frecvență impară.
Date de intrare
Fișierul de intrare frecvimp.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.
Date de ieşire
Fișierul de ieșire frecvimp.out va conține pe prima linie numărul p, reprezentând singura valoare din șirul dat care este putere a lui 2 și are frecvență impară.
Restricții și precizări
- 1 ⩽ n ⩽ 1.000.000
- numerele de pe a doua linie a fișierului de intrare sunt naturale, nenule și mai mici decât
- = 2 63 - 1
Exemplu
- frecvimp.in
- 10
- 41 235 64 41 512 64 1488 512 361 512
- frecvimp.out
- 512
Explicație
În fișierul de intrare sunt 2 puteri ale lui 2, 64 și 512, dintre care 512 apare de 3 ori.
Rezolvare
# Definim funcția
def FrecvImp(n):
# Inițializăm un dicționar gol
frec = {}
# Parcurgem lista de numere
for n in n:
# Dacă numărul nu se află încă în dicționar, îl adăugăm cu frecvența 0
if n not in frec:
frec[n] = 0
# Incrementăm frecvența numărului curent
frec[n] += 1
# Parcurgem dicționarul
for n in frec:
# Verificăm dacă frecvența numărului curent este impară și dacă numărul este o putere a lui 2
if frec[n] % 2 == 1 and (n & (n - 1) == 0):
# Dacă găsim un astfel de număr îl returnăm
return n
# Deschidem fișierul de intrare și citim datele
with open('frecvimp.in', 'r') as intrare:
n = int(intrare.readline())
# Citim a doua linie, o împărțim în cuvinte separate prin spații și convertim fiecare cuvânt la int
numere = list(map(int, intrare.readline().split()))
# Apelăm funcția
result = FrecvImp(numere)
# Deschidem fișierul de ieșire și scriem rezultatul
with open('frecvimp.out', 'w') as iesire:
iesire.write(str(result))