2714 - Frecv Imp: Diferență între versiuni
De la Universitas MediaWiki
Fără descriere a modificării |
|||
Linia 11: | Linia 11: | ||
== Exemplul 1 == | == Exemplul 1 == | ||
; frecvimpin.txt | ; frecvimpin.txt | ||
10 | |||
41 235 64 41 512 64 1488 512 361 512 | |||
; frecvimpout.txt | ; frecvimpout.txt | ||
Datele de intrare corespund restrictiilor impuse | |||
512 | |||
<br> | <br> | ||
== Exemplul 2 == | == Exemplul 2 == | ||
; frecvimpin.txt | ; frecvimpin.txt |
Versiunea de la data 15 noiembrie 2023 18:07
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 frecvimpin.txt 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 frecvimpout.txt 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
Exemplul 1
- frecvimpin.txt
10 41 235 64 41 512 64 1488 512 361 512
- frecvimpout.txt
Datele de intrare corespund restrictiilor impuse 512
Exemplul 2
- frecvimpin.txt
- -1
- 22 77 99 11
- frecvimp.out
- Datele de intrare nu corespund restrictiilor impuse
Explicație
În fișierul de intrare sunt 2 puteri ale lui 2, 64 și 512, dintre care 512 apare de 3 ori.
Rezolvare
# 2714 Frecv Imp
def validare(n_validare, numere_validare):
# Verificăm dacă n este în intervalul 1-1000000
if n_validare < 1 or n_validare > 1000000:
raise ValueError # Ridicăm o eroare dacă n nu este în intervalul 1-1000000
for numar in numere_validare: # Parcurgem lista de numere
if numar < 1 or numar > 9223372036854775807:
# Ridicăm o eroare dacă numărul nu este în intervalul 1-9223372036854775807
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")
def frecvimp(numere):
frec = {} # Inițializăm un dicționar gol
for numar in numere: # Parcurgem lista de numere
# Dacă numărul nu se află încă în dicționar, îl adăugăm cu frecvența 0
if numar not in frec:
frec[numar] = 0
frec[numar] += 1 # Incrementăm frecvența numărului curent
for numar in frec: # Parcurgem dicționarul
# Dacă frecvența numărului curent este impară și dacă numărul este o putere a lui 2
if frec[numar] % 2 == 1 and (numar & (numar - 1) == 0):
return numar # Dacă găsim un astfel de număr îl returnăm
if __name__ == '__main__':
file_in = open("frecvimpin.txt", "r") # Deschidem fișierul de intrare pentru citire
file_out = open("frecvimpout.txt", "w") # Deschidem fișierul de ieșire pentru scriere
try:
# Citim numărul de numere
n_main = int(file_in.readline())
# Citim numerele
numere_main = list(map(int, file_in.readline().split()))
validare(n_main, numere_main) # Validăm datele de intrare
# Calculăm și scriem numărul cu frecvență impară
rezultat_main = frecvimp(numere_main)
file_out.write(str(rezultat_main) + '\n')
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")