2714 - Frecv Imp

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 $9223372036854775807$
• $9223372036854775807$ = 2 ⁶³ - 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

<syntaxhighlight lang="python" line>

1. 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")

</syntaxhighlight>