2714 - Frecv Imp: Difference between revisions

From Bitnami MediaWiki
Pagină nouă: == 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 co...
 
mNo edit summary
Line 8: Line 8:
* 1 les; n ⩽ 1.000.000
* 1 les; 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>
* <math> 9223372036854775807 = 2 <sup> 63 </sup> - 1
* <math> 9223372036854775807 = 2 <sup> 63 </sup> - 1 </math>
== Exemplu ==
== Exemplu ==
; frecvimp.in
; frecvimp.in

Revision as of 12:17, 28 October 2023

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 les; n ⩽ 1.000.000
  • numerele de pe a doua linie a fișierului de intrare sunt naturale, nenule și mai mici decât

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

<syntaxhighlight lang="python" line>

  1. 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
  1. 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()))
  1. Apelăm funcția

result = FrecvImp(numere)

  1. Deschidem fișierul de ieșire și scriem rezultatul

with open('frecvimp.out', 'w') as iesire:

   iesire.write(str(result))

</syntaxhighlight>